首页 > 代码库 > poj 1952 BUY LOW, BUY LOWER 最长下降子序列+统计不重复方案数
poj 1952 BUY LOW, BUY LOWER 最长下降子序列+统计不重复方案数
dp[i]=max(dp[i],dp[j]+1) j<i且a[j]>a[i]
dp[i]表示长度为i的最长下降子序列的长度。
r[i]表示长度为i的最长下降子序列的方案数。
考虑这样一个问题,比如6 3 9 3,对于两个3,他们数字一样并且dp值也一样,那么r[2]的方案数是没有意义的
因为能通过第一个3扩展的也能通过第二个3扩展,所以直接把r[2]=0。
对于一次扩展若dp[j]+1==dp[i],则说明j的路线和i的路线都可以用则r[i]+=r[j]
若dp[j]+1>dp[i],则更新答案,路线就是从j过来的,r[i]=r[j]
#include<cstdio> #include<algorithm> #include<iostream> using namespace std; #define MAXN 100005 #define INF 0x3f3f3f3f int a[MAXN],dp[MAXN],r[MAXN],n; int main() { while(~scanf("%d",&n)) { int ans1=0,ans2=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); r[i]=1; dp[i]=1; } for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) { if(a[j]>a[i]) { if(dp[j]+1>dp[i]) { dp[i]=dp[j]+1; r[i]=r[j]; } else if(dp[j]+1==dp[i]) { r[i]+=r[j]; } } } for(int j=1;j<i;j++) { if(a[j]==a[i]&&dp[j]==dp[i]) r[j]=0; } ans1=max(ans1,dp[i]); } for(int i=1;i<=n;i++) { if(dp[i]==ans1) ans2+=r[i]; } printf("%d %d\n",ans1,ans2); } return 0; } /* 6 5 2 3 2 4 2 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。