sdut 3565 Feed the monkey (有限制 (2)dp)-------C语言—菜鸟级

Fivecc

发布于 2022-11-21 15:00:54

2520

发布于 2022-11-21 15:00:54

文章被收录于专栏：前端ACE

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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-05-22，如有侵权请联系 cloudcommunity@tencent.com 删除