【题解】洛谷P1020[NOIP1999普及]导弹拦截 线性DP
#include<cstdio>
#include<algorithm>
using namespace std;
int a[1010],b[1010],c[1010];
int main(){
//freopen("in.txt","r",stdin);
int cnt=0,maxn=1,i,j;
while(scanf("%d",&a[cnt++])!=EOF)
for(i=0;i<cnt;i++){
b[i]=1;
for(j=0;j<i;j++)
if(a[i]<=a[j]&&b[j]+1>b[i])b[i]=b[j]+1;
maxn=max(maxn,b[i]);
}
printf("%d\n",maxn);
maxn=1;
for(i=0;i<cnt;i++){
c[i]=1;
for(j=0;j<i;j++)
if(a[i]>a[j]&&c[j]+1>c[i])c[i]=c[j]+1;
maxn=max(maxn,c[i]);
}
printf("%d\n",maxn);
return 0;
}
总结
无