【题解】洛谷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;
}

总结

无