HDU2614 DFS

题意

有一些题目，给出二维数组a[][]，a[i][j]指在做完i题之后做j题需要用的时间。后做的题的时间要求比先做的题要长，并且总是先用0分钟完成第0题。求最多能做的题数

解法

从a[0][0]开始深搜，dfs记录三个值：1深度。2上一题。3上一题时间。记录最深的深度作为答案。 #include<cstdio> #include<cstring> int map[15][15]; int vis[15]; int n,ans; void dfs(int depth,int time,int i)//i means :after solved i problem { if(depth > ans) ans = depth; for(int j=1;j<n;j++) { if(vis[j]) continue; else if(map[i][j] >= time) { vis[j] = true; dfs(depth+1,map[i][j],j); vis[j] = false; } } } int main() { while(~scanf("%d",&n)) { ans = 0; memset(vis,false,sizeof(vis)); for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",map[i]+j); vis[0] = true; dfs(1,0,0); printf("%d\n",ans); } }