sdut3565Feedthemonkey(有限制(2)dp)

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

#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("%lld\n",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("%lld\n",ans);
    }
    return 0;
}