首页 > 代码库 > 拦截导弹 （NYOJ—79）
拦截导弹 （NYOJ—79）
这是到动态规划的题目，属于有顺序的0 1 背包问题；
代码：
1 #include<stdio.h> 2 #include<string.h> 3 4 int d[20][100000]; //d[i][j] 5 int a[20]; 6 int N; 7 8 int max(int a, int b) 9 {10 return a>b?a:b;11 }12 13 int solve(int i,int high)14 {15 if(d[i][high]>=0)16 return d[i][high];17 if(i==N)18 {19 if(a[i]<high)20 return d[N][high]=1;21 else22 return d[N][high]=0;23 }24 if(a[i]<high)25 return d[i][high]=max(solve(i+1,a[i])+1,solve(i+1,high)); //打击和不打击 取大者26 else27 return d[i][high]=solve(i+1,high);28 }29 30 int main()31 {32 int T;33 scanf("%d",&T);34 while(T--)35 {36 memset(d,-1,sizeof(d));37 scanf("%d",&N);38 for(int i=1; i<=N; i++)39 {40 scanf("%d",&a[i]);41 }42 printf("%d\n",solve(0,9999));43 }44 return 0;45 }
但这个代码提交会得到RE，至于为什么可能是记忆话搜索对这个的复杂度减小的比较小，所以递归深度太深，造成堆栈溢出。
我想多了，不是这个原因，是我没有注意到下标越界了。
AC代码：
1 #include<stdio.h> 2 #include<string.h> 3 4 int d[22][1000]; //d[i][j] 5 int a[22]; 6 int N; 7 8 int max(int a, int b) 9 {10 return a>b?a:b;11 }12 13 int solve(int i,int high)14 {15 if(d[i][high]>=0)16 return d[i][high];17 if(i==N)18 {19 if(a[i]<high)20 return d[N][high]=1;21 else22 return d[N][high]=0;23 }24 if(a[i]<high)25 return d[i][high]=max(solve(i+1,a[i])+1,solve(i+1,high)); //打击和不打击 取大者26 else27 return d[i][high]=solve(i+1,high);28 }29 30 int main()31 {32 int T;33 scanf("%d",&T);34 while(T--)35 {36 memset(d,-1,sizeof(d));37 scanf("%d",&N);38 for(int i=1; i<=N; i++)39 {40 scanf("%d",&a[i]);41 }42 printf("%d\n",solve(1,999));43 }44 return 0;45 }
拦截导弹 （NYOJ—79）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。