首页 > 代码库 > Ural 2018The Debut Album(DP)
Ural 2018The Debut Album(DP)
题目地址:Ural 2018
简单DP。用滚动数组。
代码如下:
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; #define LL __int64 const int INF=0x3f3f3f3f; const int mod=1e9+7; int dp[3][3][400]; int main() { int n, a, b, i, j; memset(dp,0,sizeof(dp)); scanf("%d%d%d",&n,&a,&b); if(n==1) printf("2\n"); else { dp[1][0][1]=1; dp[1][1][1]=1; for(i=2; i<=n; i++) { memset(dp[i&1],0,sizeof(dp[i&1])); for(j=1;j<=b;j++) { dp[i&1][0][1]+=dp[i+1&1][1][j]; if(dp[i&1][0][1]>=mod) dp[i&1][0][1]%=mod; if(j==1) continue ; dp[i&1][1][j]+=dp[i+1&1][1][j-1]; if(dp[i&1][1][j]>=mod) dp[i&1][1][j]%=mod; } for(j=1;j<=a;j++) { dp[i&1][1][1]+=dp[i+1&1][0][j]; if(dp[i&1][1][1]>=mod) dp[i&1][1][1]%=mod; if(j==1) continue ; dp[i&1][0][j]+=dp[i+1&1][0][j-1]; if(dp[i&1][0][j]>=mod) dp[i&1][0][j]%=mod; } } int ans=0; for(i=1;i<=a;i++) { ans+=dp[n&1][0][i]; if(ans>=mod) ans%=mod; } for(i=1;i<=b;i++) { ans+=dp[n&1][1][i]; if(ans>=mod) ans%=mod; } printf("%d\n",ans); } return 0; }
Ural 2018The Debut Album(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。