SDUT 3565 Feed the monkey(DP)
4371 단어 DP
제목: 세 가지 과일의 수량과 한 과일의 연속할 수 없는 수량을 드리겠습니다. 몇 가지 조합 방식이 있는지 물어보세요.
사고방식: 기억화 검색, dp[num1][num2][num3][pre][con],num1num2num3은 세 가지 과일의 잉여수를 표시하고,pre는 위에 놓은 것을 표시한다.
어떤 과일인지 콘은 지난 과일이 며칠째 놓여 있는지 나타낸다.
코드:
#include
#include
#include
using namespace std;
const int maxn = 55;
const int mod = 1e9+7;
int dp[maxn][maxn][maxn][3][maxn];
int n1, n2, n3, d1, d2, d3;
int dfs(int num1, int num2, int num3, int pre, int con)
{
if(num1 < 0 || num2 < 0 || num3 < 0) return 0;
if((pre==0&&con>d1) || (pre==1&&con>d2) || (pre==2&&con>d3)) return 0;
if(!num1 && !num2 && !num3) return 1;
if(dp[num1][num2][num3][pre][con] != -1) return dp[num1][num2][num3][pre][con];
int ans = 0;
if(pre == 0)
{
ans = (ans+dfs(num1-1, num2, num3, 0, con+1))%mod;
ans = (ans+dfs(num1, num2-1, num3, 1, 1))%mod;
ans = (ans+dfs(num1, num2, num3-1, 2, 1))%mod;
}
else if(pre == 1)
{
ans = (ans+dfs(num1-1, num2, num3, 0, 1))%mod;
ans = (ans+dfs(num1, num2-1, num3, 1, con+1))%mod;
ans = (ans+dfs(num1, num2, num3-1, 2, 1))%mod;
}
else
{
ans = (ans+dfs(num1-1, num2, num3, 0, 1))%mod;
ans = (ans+dfs(num1, num2-1, num3, 1, 1))%mod;
ans = (ans+dfs(num1, num2, num3-1, 2, con+1))%mod;
}
return dp[num1][num2][num3][pre][con] = ans;
}
int main(void)
{
int t;
cin >> t;
while(t--)
{
memset(dp, -1, sizeof(dp));
scanf("%d%d%d%d%d%d", &n1, &n2, &n3, &d1, &d2, &d3);
int 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;
printf("%d
", ans);
}
return 0;
}
Feed the monkey
Time Limit: 2000MS
Memory Limit: 131072KB
Submit Statistic Discuss
Problem Description
Alice has a monkey, she must feed fruit to the monkey every day.She has three kinds of fruits, bananas, peaches and apples. Every day, she chooses one in three, and pick one of this to feed the monkey. But the monkey is picky, it doesn’t want bananas for more than D1 consecutive days, peaches for more than D2 consecutive days, or apples for more than D3 consecutive days. Now Alice has N1 bananas, N2 peaches and N3 apples, please help her calculate the number of schemes to feed the monkey.
Input
Multiple test cases. The first line contains an integer T (T<=20), indicating the number of test case. Each test case is a line containing 6 integers N1, N2, N3, D1, D2, D3 (N1, N2, N3, D1, D2, D3<=50).
Output
One line per case. The number of schemes to feed the monkey during (N1+N2+N3) days. The answer is too large so you should mod 1000000007.
Example Input
1
2 1 1 1 1 1
Example Output
6
Hint
Answers are BPBA, BPAB, BABP, BAPB, PBAB, and ABPB(B-banana P-peach A-apple)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.