首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。