1642: 题目 D Feed the monkey 题目描述
爱丽丝有一只猴子，她必须每天给猴子喂水果。她有三种水果，香蕉，桃子和苹果。每天，她都会选择三分之一，
然后选择其中一种喂猴子。但是猴子是很挑剔的，它不希望香蕉连续吃超过D1天，桃子连续超过吃D2天，或苹果连续吃D3天以上。现在爱丽丝有N1香蕉，N2桃子和N3。苹果，请帮她计算一下喂猴子的计划。
现在爱丽丝有N1香蕉，N2桃子和N3。苹果，请帮她计算一下喂猴子的计划。
输入
多个测试用例。第一行包含一个整数T (T<=20)，表示测试用例的数量。
每个测试用例是一个包含6个整数N1、N2、N3、D1、D2、D3 (N1、N2、N3、D1、D2、D3<=50)。
输出
输出一行。在(N1 N2 N3)天内喂养猴子的计划数目。答案太大了，所以你应该对1000000007取模。
样例输入 1 2 1 1 1 1 1
样例输出 6
代码语言：javascript复制#include<stdio.h>
#include<string.h>
#define N 51
#define MOD 1000000007
#define min(a,b) a>b?b:a
typedef long long ll;
int main()
{ int T,n1,n2,n3,x1,x2,x3;
long int dp[N][N][N][4]; int tem,i,j,k,s;
scanf("%d",&T);
while(T--)
{ ll ans=0;
memset(dp,0,sizeof(dp));
scanf("%d%d%d%d%d%d",&n1,&n2,&n3,&x1,&x2,&x3);
for(i=n1;i>=0;i--)
for(j=n2;j>=0;j--)
for(k=n3;k>=0;k--)
{ tem=min(i,x1);
for(s=1;s<=tem;s )
if(i==n1&&j==n2&&k==n3)dp[i-s][j][k][1]=(dp[i][j][k][1] 1)%MOD;
else dp[i-s][j][k][1]=(dp[i-s][j][k][1] (dp[i][j][k][2] dp[i][j][k][3])%MOD)%MOD;
tem=min(j,x2);
for(s=1;s<=tem;s )
if(i==n1&&j==n2&&k==n3)dp[i][j-s][k][2]=(dp[i][j][k][2] 1)%MOD;
else dp[i][j-s][k][2]=(dp[i][j-s][k][2] (dp[i][j][k][1] dp[i][j][k][3])%MOD)%MOD;
tem=min(k,x3);
for(s=1;s<=tem;s )
if(i==n1&&j==n2&&k==n3)dp[i][j][k-s][3]=(dp[i][j][k][3] 1)%MOD;
else dp[i][j][k-s][3]=(dp[i][j][k-s][3] (dp[i][j][k][1] dp[i][j][k][2])%MOD)%MOD;
}
ans=(dp[0][0][0][1] dp[0][0][0][2] dp[0][0][0][3])%MOD;
printf("%lldn",ans);
}
return 0;
}#include<stdio.h>
#include<string.h>
#define N 51
#define MOD 1000000007
typedef long long ll;
int vis[N][N][N][N][3];int x1,x2,x3,tem;
int DFS(int n1,int n2,int n3,int cot,int lost)
{
if(cot==0||n1<0||n2<0||n3<0)return 0;
if(vis[n1][n2][n3][cot][lost]!=-1)return vis[n1][n2][n3][cot][lost];
if(n1 n2 n3==0)return vis[n1][n2][n3][cot][lost]=1;
ll ans=0;int t[3]={0};t[lost]=cot;
if(t[0]<x1)ans=DFS(n1-1,n2,n3,t[0] 1,0)%MOD;
if(t[1]<x2)ans=(ans DFS(n1,n2-1,n3,t[1] 1,1))%MOD;
if(t[2]<x3)ans=(ans DFS(n1,n2,n3-1,t[2] 1,2))%MOD;
return vis[n1][n2][n3][cot][lost]=ans;
}
int main()
{ int T, n1,n2,n3;
scanf("%d",&T);
while(T--)
{ ll ans=0;
memset(vis,-1,sizeof(vis));
scanf("%d%d%d%d%d%d",&n1,&n2,&n3,&x1,&x2,&x3);
ans=DFS(n1-1,n2,n3,1,0)%MOD;
ans=(ans DFS(n1,n2-1,n3,1,1))%MOD;
ans=(ans DFS(n1,n2,n3-1,1,2))%MOD;
printf("%lldn",ans);
}
return 0;
}
