题目链接
思路:
dp[i][j][k][a][b] 表示i个B j个P K 个A 选择第a种水果 连续选择了b个的种数,即可得到转移方程.
最后我们记录所有以其中任何一种水果结尾的连续的i个的种类.
以此时放B为例:
我们枚举可连续放B的个数b,可得到如下的转移方程:
1.继续放B 则 dp[i+1][j][k][a][b+1]=(dp[i+1][j][k][a][b+1]+dp[i][j][k][a][b])
2.放P
dp[i][j+1][k][1][1]=(dp[i][j+1][k][1][1]+dp[i][j][k][a][b])%MOD;3.放A
dp[i][j][k+1][2][1]=(dp[i][j][k+1][2][1]+dp[i][j][k][a][b])%MOD;PS：
一开始这个题我真的没想明白要怎么去转移,当时思维有点混乱,只想了5维dp,想了一下复杂度觉得还可以,转移的时候就开始乱想了,搜了一发题解发现都是用记忆化搜索写的,本人最弱的就是记忆化搜索,除了会套数位dp的板子.
#include<bits/stdc++.h> #define Ri(a) scanf("%d", &a) #define Rl(a) scanf("%lld", &a) #define Rf(a) scanf("%lf", &a) #define Rs(a) scanf("%s", a) #define Pi(a) printf("%d\n", (a)) #define Pf(a) printf("%lf\n", (a)) #define Pl(a) printf("%lld\n", (a)) #define Ps(a) printf("%s\n", (a)) #define W(a) while(a--) #define CLR(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define inf 0x3f3f3f3f #define exp 0.00000001 #define pii pair<int, int> #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn=1e5+10; int dp[55][55][55][5][55]; int n1,n2,n3,d1,d2,d3; int main() { int t; Ri(t); W(t) { Ri(n1),Ri(n2),Ri(n3),Ri(d1),Ri(d2),Ri(d3); CLR(dp,0); dp[1][0][0][0][1]=1; dp[0][1][0][1][1]=1; dp[0][0][1][2][1]=1; for(int i=0;i<=n1;i++) { for(int j=0;j<=n2;j++) { for(int k=0;k<=n3;k++) { if(i==0&&j==0&&k==0) continue; for(int a=0;a<=2;a++) { if(a==0) { for(int b=1;b<=min(i,d1);b++) { if(b+1<=d1) dp[i+1][j][k][a][b+1]=(dp[i+1][j][k][a][b+1]+dp[i][j][k][a][b])%MOD; dp[i][j+1][k][1][1]=(dp[i][j+1][k][1][1]+dp[i][j][k][a][b])%MOD; dp[i][j][k+1][2][1]=(dp[i][j][k+1][2][1]+dp[i][j][k][a][b])%MOD; } } if(a==1) { for(int b=1;b<=min(j,d2);b++) { if(b+1<=d2) dp[i][j+1][k][a][b+1]=(dp[i][j+1][k][a][b+1]+dp[i][j][k][a][b])%MOD; dp[i+1][j][k][0][1]=(dp[i+1][j][k][0][1]+dp[i][j][k][a][b])%MOD; dp[i][j][k+1][2][1]=(dp[i][j][k+1][2][1]+dp[i][j][k][a][b])%MOD; } } if(a==2) { for(int b=1;b<=min(k,d3);b++) { if(b+1<=d3) dp[i][j][k+1][a][b+1]=(dp[i][j][k+1][a][b+1]+dp[i][j][k][a][b])%MOD; dp[i+1][j][k][0][1]=(dp[i+1][j][k][0][1]+dp[i][j][k][a][b])%MOD; dp[i][j+1][k][1][1]=(dp[i][j+1][k][1][1]+dp[i][j][k][a][b])%MOD; } } } } } } ll ans=0; for(int i=1;i<=d1;i++) ans=(ans+dp[n1][n2][n3][0][i])%MOD; for(int i=1;i<=d2;i++) ans=(ans+dp[n1][n2][n3][1][i])%MOD; for(int i=1;i<=d3;i++) ans=(ans+dp[n1][n2][n3][2][i])%MOD; Pl(ans); } return 0; } 记忆化搜索:
#include<bits/stdc++.h> #define ll long long #define mod 1000000007 using namespace std; ll dp[55][55][55][5][55]; int n1,n2,n3,d1,d2,d3; ll dfs(int a,int b,int c,int t,int e) { if(a<0||b<0||c<0) return 0; if(t==0&&e>d1||t==1&&e>d2||t==2&&e>d3) return 0; if(a==0&&b==0&&c==0) return 1; if(dp[a][b][c][t][e]!=-1) return dp[a][b][c][t][e]; ll ans=0; if(t==0) { ans=(ans+dfs(a-1,b,c,0,e+1))%mod; ans=(ans+dfs(a,b-1,c,1,1))%mod; ans=(ans+dfs(a,b,c-1,2,1))%mod; return dp[a][b][c][t][e]=ans; } if(t==1) { ans=(ans+dfs(a-1,b,c,0,1))%mod; ans=(ans+dfs(a,b-1,c,1,e+1))%mod; ans=(ans+dfs(a,b,c-1,2,1))%mod; return dp[a][b][c][t][e]=ans; } if(t==2) { ans=(ans+dfs(a-1,b,c,0,1))%mod; ans=(ans+dfs(a,b-1,c,1,1))%mod; ans=(ans+dfs(a,b,c-1,2,e+1))%mod; return dp[a][b][c][t][e]=ans; } } int main() { int T; cin>>T; while(T--) { scanf("%d%d%d%d%d%d",&n1,&n2,&n3,&d1,&d2,&d3); memset(dp,-1,sizeof(dp)); ll ans=0; ans=(ans+dfs(n1-1,n2,n3,0,1))%mod; ans=(ans+dfs(n1,n2-1,n3,1,1))%mod; ans=(ans+dfs(n1,n2,n3-1,2,1))%mod; cout<<ans<<endl; } return 0; }
Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
