学步园

解题思路： 一开始没有想到是最大不减子序列，但是后来看了别人的解题报告并且自己分析了一下，真的就是最长不减子序列！用dp[i]表示第i个位置上的所需要的导弹系统数量！把它当做最简单的LIS做就ac了！后来我仔细考虑了一下，改了一下，结果却wa了！不知道怎么回事！还是以后再来再想想吧---- 下面是ac代码：完全是当做LIS做的：

#include<iostream><br /> #include<cstdlib><br /> #include<cstdio><br /> using namespace std;<br /> int dp[10000];<br /> int main()<br /> {<br /> int N,i,j,a[10000],maxtemp;<br /> while(scanf("%d",&N)!=EOF)<br /> {<br /> for(i=0;i<N;i++)<br /> scanf("%d",&a[i]);<br /> dp[0]=1;<br /> for(i=1;i<N;i++)<br /> {<br /> maxtemp=0;<br /> for(j=0;j<i;j++)<br /> {<br /> if(a[i]>=a[j]&&dp[j]>maxtemp)<br /> maxtemp=dp[j];<br /> }<br /> dp[i]=maxtemp+1;<br /> printf("dp[%d]=%d/n",i,dp[i]);<br /> }<br /> maxtemp=0;<br /> for(i=0;i<N;i++)<br /> maxtemp=max(maxtemp,dp[i]);<br /> printf("%d/n",maxtemp);<br /> }<br /> return 0;<br /> }

后来自己重新考虑了一下写了个另外的代码，但是交上去挖了：

牛人如果愿意看看是什么原因，希望可以得到牛人的提示留言，谢谢：

#include<iostream><br /> #include<cstdlib><br /> #include<cstdio><br /> using namespace std;<br /> int dp[100];<br /> int main()<br /> {<br /> int N,i,j,k,a[100],maxtemp;<br /> while(scanf("%d",&N)!=EOF)<br /> {<br /> for(i=0;i<N;i++)<br /> scanf("%d",&a[i]);<br /> dp[0]=1;<br /> for(i=1;i<N;i++)<br /> {<br /> maxtemp=0;<br /> if(a[i]>=a[i-1])<br /> {<br /> for(k=0;k<i;k++)<br /> maxtemp=max(maxtemp,dp[k]);<br /> }<br /> dp[i]=maxtemp+1;<br /> // printf("dp[%d]=%d/n",i,dp[i]);<br /> }<br /> maxtemp=0;<br /> for(i=0;i<N;i++)<br /> maxtemp=max(maxtemp,dp[i]);<br /> printf("%d/n",maxtemp);<br /> }<br /> return 0;<br /> }

谢谢---