LightOJ 1145 Dice (I) dp

題目連結：LightOJ 1145

題意：

有n個骰子，每個骰子有k個面，每個面有一個權值，為該面的下标，現在用用n個骰子湊出面值s，問有多少種方法。

思路：

設dp[i][j]表示第i個骰子湊出了j有dp[i][j]種方法。

那麼dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + … + dp[i-1][j-k]

那麼狀态有n*s個，轉移花費k，顯然會逾時。

觀察發現：

dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + … + dp[i-1][j-k]

dp[i][j-1] = dp[i-1][j-2] + dp[i-1][j-3] + … + dp[i-1][j-k-1]

聯立一下得到：

dp[i][j] = dp[i][j-1] - dp[i-1][j-k-1] + dp[i-1][j-1]

這樣轉移就是O(1)了。

然後MLE了。。。

n*s = 1500W * 4byte = 60 000 000 byte = 60MB > 32MB

再次觀察發現每次隻用到dp[i]和dp[i-1]，這樣可以用dp[2][s]大的數組滾動處理就可以了。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

long long dp[][];
const int mod = ;

int main(){
    int t, n, k, s, Case=;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d%d", &n, &k, &s);

        for(int i=; i<=k; ++i) dp[][i] = ;
        for(int i=k+; i<=s; ++i) dp[][i] = ;

        for(int i=; i<=n; ++i){
            for(int j=; j<=s; ++j){
                if(j-k->=)
                    dp[i&][j] = ((dp[i&][j-] + dp[(i-)&][j-])%mod + mod - dp[(i-)&][j-k-]) % mod;
                else
                    dp[i&][j] = ((dp[i&][j-] + dp[(i-)&][j-])%mod + mod - dp[(i-)&][]) % mod;
            }
        }
        printf("Case %d: %lld\n", ++Case, dp[n&][s]);
    }
    return ;
}