H - 无聊的小明 HRBUST - 2181 [数位DP] 学习中ing
| 无聊的小明 | ||||||
| ||||||
| Description | ||||||
小明想用两个字母a和b创造一个长度为n的单词，但是他又不希望连续的a超过p个，同时也不希望连续的b超过q个。那么小明有能创造出多少个不用的单词呢？ | ||||||
| Input | ||||||
每组数据包括一行，三个整数n，p，q分别对应题意。 其中max(a, b) <= n <= 50000，1 <= a, b <= 300。 | ||||||
| Output | ||||||
输出不同的单词的个数。个数要对1000000007取模。 | ||||||
| Sample Input | ||||||
3 2 1 | ||||||
| Sample Output | ||||||
4 | ||||||
| Source | ||||||
| 2014.11.29新生赛-热身赛 |
思路：
1.定义DP[n][0] ： 长度为n的，当前字母为0的方案数
那么有 dp[n][0]=sigma dp[i-j][1] j∈[n-p,i-1];
dp[n][1]=sigma dp[i-j][0] j∈[n-p,i-1];
AC代码：
#include <stdio.h>
#include <string.h>
typedef long long ll;
const int MAX_N=1e3+3;
const int MOD=1e9+7;
ll dp[50005][3];
int main(void){
int n,p,q;
while(~(scanf("%d%d%d",&n,&p,&q))){
memset(dp,0,sizeof(dp));
dp[0][0]=dp[0][1]=1;
for(int i=1;i<=n;++i){
// int t=max(0,i-p);
// for(int j=t;j<=i-1;j++) dp[i][0]=(dp[i][0]%MOD+dp[j][1]%MOD)%MOD;
// t=max(0,i-q);
// for(int j=t;j<=i-1;j++) dp[i][1]=(dp[i][1]%MOD+dp[j][0]%MOD)%MOD;
for(int j=1;j<=p&&j<=i;++j) dp[i][0]+=dp[i-j][1],dp[i][0]%=MOD;
for(int j=1;j<=q&&j<=i;++j) dp[i][1]+=dp[i-j][0],dp[i][1]%=MOD;
}
// for(int i=0;i<=10;i++) printf("%d %d\n",dp[i][0],dp[i][1]);
printf("%lld\n",(dp[n][0]+dp[n][1])%MOD);
}
}
爱玛科技成长空间 4人发布