首页 > 代码库 > Hdu5087Revenge of LIS II简单dp

Hdu5087Revenge of LIS II简单dp

有个坑点,就是转移的时候前面状态数量如果不同,后面即使从同一个点转移过来,也是不同的。

#include<iostream>#include<cstdio>#include<cstring>#include<map>#include<vector>#include<stdlib.h>using namespace std;typedef long long LL;const LL maxn = 1111;LL dp[maxn];LL dp1[maxn];LL cnt[maxn];LL a[maxn];int main(){    LL T;    LL n;    cin>>T;    while(T--){        cin>>n;        for(LL i =1;i<=n;i++)            cin>>a[i];        for(LL i =1;i<=n;i++){            dp[i]=1;            for(LL j=1;j<i;j++)                if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);        }        for(LL i =1;i<=n;i++){            dp1[i]= 1;if(dp1[i]==dp[i]) cnt[i] =1;else cnt[i] = 0;            for(LL j=1;j<i;j++){                if(a[i]>a[j]){                    if(dp1[i]<=dp1[j]+1&&dp1[j]+1==dp[i]) cnt[i]+=cnt[j];                    if(dp1[i]<dp1[j]+1) dp1[i]=dp1[j]+1;                }            }        }        LL ans=0;        LL Max= - 1;        for(LL i=1;i<=n;i++)            if(Max<dp[i]) Max =dp[i];        for(LL i=1;i<=n;i++)            if(dp[i]==Max) ans+=cnt[i];        if(ans==1) cout<<Max-1<<endl;        else cout<<Max<<endl;    }    return 0;}

 

Hdu5087Revenge of LIS II简单dp