lightoj1145 【DP优化求方案】

题意：

有一个k面的骰子，然后问你n个骰子朝上的面数字之和=s的方案；

思路：

dp[i][j] 代表前 i 个骰子组成 j 有多少种方案；

显然

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j - 2] + ... + dp[i - 1][j - k];

我们算 dp[i][j] 的时候，需要dp[i-1] 的前缀和已经打出来了

我们求dp[i][j] 的时候，要求出 dp[i][j] 的前缀和，提供给求 i+1 的时候使用；

还有第二种方法：wonter

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int>PII;

const double eps=1e-5;

const double pi=acos(-1.0);

const int INF=0x3f3f3f3f;

const int mod=100000007;

const int N=15000+10;

int n,k,s;

int dp[N];

int sum[2][N];

int main()

{

    int T,cas=1;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%d",&n,&k,&s);

        memset(sum,0,sizeof(sum));

        memset(dp,0,sizeof(dp));

        for(int i=0;i<=s;i++)

            sum[0][i]=1;

        for(int i=1;i<=n;i++)

        {

            sum[i&1][0]=0;

            for(int j=1;j<=s;++j)

            {

                int l,r;

                l=max(0,j-k);

                r=j-1;

                if(l-1<0)

                    dp[j]=sum[(i-1)&1][r];

                else

                    dp[j]=(sum[(i-1)&1][r]-sum[(i-1)&1][l-1]+mod)%mod;

                sum[i&1][j]=(sum[i&1][j-1]+dp[j])%mod;

            }

        }

        printf("Case %d: %d\n",cas++,dp[s]);

    }

    return 0;

}

/*

5

1 6 3

2 9 8

500 6 1000

800 800 10000

2 100 10

*/

巴特西

lightoj1145 【DP优化求方案】

最新文章

热门文章