Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
真心不明白为什么tle,有高手帮我看一下吗?#include<iostream> #include<algorithm> using namespace std; int sticks[25], mark[25], side, M; bool ok; int comp(int a, int b) { return a > b; } void dfs(int cur, int left, int sideNum) { int i; if(sideNum == 4) { ok = true; return; } for(i = cur; i < M; i++) { if(mark[i] == 1) continue; if(i > 0) { if(sticks[i] == sticks[i-1] && mark[i-1] == 0) continue; } if(left < sticks[i]) continue; mark[i] = 1; if(sticks[i] == left) { int temp; for(temp = 0; mark[temp] == 1; temp++); dfs(temp, side, sideNum+1); } else dfs(cur+1, left-sticks[i], sideNum); if(ok) return; mark[i] = 0; if(left == sticks[i] || left == side) return; } return; } int main() { int N, sum; scanf("%d", &N); while(N--) { scanf("%d", &M); //init sum = 0; ok = false; memset(mark, 0, sizeof(mark)); for(int i = 0; i < M; i++) { scanf("%d", &sticks[i]); sum += sticks[i]; } //枝剪1 if(sum % 4 != 0) { printf("no\n"); continue; } side = sum / 4; //先进行排序再深搜 sort(sticks, sticks+M, comp); //枝剪2 if(sticks[0] > side) { printf("no\n"); continue; } dfs(0, side, 0); if(ok) printf("yes\n"); else printf("no\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator