SDUT__汤圆系列之迷の汤圆序列

迷の汤圆序列

Time Limit: 1000MS Memory limit: 65536K

数位dp；

题目描述

        又到了汤圆星球一年一度的汤圆节了，汤圆是汉族传统小吃的代表之一，是由糯米粉等做的球形食品，一般有馅料，煮熟带汤吃，同时也是

元宵节最具有特色的食物。历史十分悠久。据传，汤圆起源于宋朝。当时明州（现浙江省宁波市）兴起吃一种新奇食品，即用黑芝麻、油做馅、

加入少许白砂糖，外面用糯米粉搓成球，煮熟后，吃起来香甜可口，饶有风趣。因为这种糯米球煮在锅里又浮又沉，所以它最早叫“浮元子”，后

来有的地区把“浮元子”改称元宵。据说元宵象征合家团圆更美好，吃元宵意味新的一年合家幸福、团团圆圆，所以正月十五元宵必备。

         到汤圆节，汤圆星人准备买n个汤圆，现在有白色和紫色两种颜色的汤圆，汤圆星人准备把它们排成一列，但是在汤圆星人的印象中如果连

续的白色汤圆超过a个或者连续的紫色汤圆超过b个就是变的不吉利，汤圆星人就会伤心，所以汤圆星人想知道吉利的序列有多少种。

输入

多组输入，每组输入三个整数n,a,b(1<=a,b<=300,max(a+b)+1<=n<=10000).

输出

输出序列的个数，由于结果比较大，对10^9+7取模.

示例输入

3 2 1

示例输出

4

提示

来源

绝尘

示例程序

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#define LL long long
using namespace std;
LL dp[10001][2][305];//长度为i，最后以j结尾的个数；
const  LL MOD=1e9+7;
int main()
{
    int n,a,b;
    while(~scanf("%d%d%d",&n,&a,&b))
    {
        memset(dp,0,sizeof(dp));
        dp[1][0][1]=1;
        dp[1][1][1]=1;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<2;j++)//以哪种颜色结尾；
            {
                for(int k=0;k<2;k++) //新添加的是那种颜色；
                {
                    if(j==0)
                    {
                        if(j==k)
                            for(int x=1;x<=a;x++)
                        {
                            (dp[i][j][x]+=dp[i-1][j][x-1])%=MOD;
                        }
                        else
                        {
                            for(int x=1;x<=a;x++)
                            {
                                (dp[i][k][1]+=dp[i-1][j][x])%=MOD;
                            }
                        }
                    }
                    else
                    {
                         if(j==k)
                            for(int x=1;x<=b;x++)
                        {
                            (dp[i][j][x]+=dp[i-1][j][x-1])%=MOD;
                        }
                        else
                        {
                            for(int x=1;x<=b;x++)
                            {
                                (dp[i][k][1]+=dp[i-1][j][x])%=MOD;
                            }
                        }
                    }
                }
            }
        }
        LL ans=0;
        for(int i=0;i<=a;i++)
        {
            (ans+=dp[n][0][i])%=MOD;
        }
        for(int i=0;i<=b;i++)
            (ans+=dp[n][1][i])%=MOD;
        printf("%lld\n",(ans));
    }
    return 0;
}