hdu1257最少拦截系统 动态规划（最长递增子序列（LIS））

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1e4+10;
int main()
{
int t,dp[maxn]={0},a[maxn]={0};
while(cin>>t)
{
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=0;i<t;i++)
scanf("%d",&a[i]);
for(int i=0;i<t;i++)
{
for(int k=i-1;k>=0;k--)
{
if(a[i]>a[k])
{
dp[i]=max(dp[i],dp[k]+1);
}
if(k==0&&dp[i]==0) dp[i]=1;
}
}
int Max=dp[0];
for(int i=0;i<t;i++)
// if(dp[i]>Max) Max=dp[i];
cout<<dp[i]<<endl;
cout<<Max<<endl;
}
return 0;
}

注意：若是使用利用第一种方法的话，如果使用滚动数组则不能知道递增数列是哪一个，当不使用滚动数组的话，可以求出最长递增子序列的各个元素。