題目鏈接：Attack on Titans ZOJ - 3747
三種士兵，G、R、P，有序排成總人數為n 的隊伍，其中要有至少m個G連續，至多k個R連續，求有多少種排列方案。
至少m個連續不好計算，但是至多m個連續好計算，只要保證沒有m個以上的連續出現就好了。那么至少m個 == 至多n個-至多m-1個
dp[i][j]：=前i個士兵，第i個為G（R，P）時，滿足至多m個G連續，至多k個R連續的方案數為dp[i]0; sum = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]; 那么，如果i<=m時，無論前面怎么擺放，第i個都可以放G，dp[i][0] = sum; 如果i==m+1，那么，前面有一種情況是1-m全是G，其他情況都可以放G，所以只需要減去第一種情況，dp[i][0] = sum - 1; 如果i>m+1，則需要減去i-m 到 i-1這一段是連續的G的情況dp[i][0] = sum - dp[i-m-1][1] - dp[i-m-1][2]
對于R同理
p沒有限制條件，放哪里都可，直接等于sum
由于方案數太大，需要對1000000007取模，wa了兩次，因為在兩個結果相減的時候沒有加上MOD再對MOD取模，導致可能出現負數，以后遇到取模后的數字相減或者其他減法，都加上一個MOD在取模保證不會出錯
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long ll;const ll MAXN = 1000000 + 100, MOD = 1000000007;ll n, m, k, dp[MAXN][3]; //GRP G>=m, R<=kll f(int m, int k)//g<=m, r<=k;{ memset(dp[0], 0, sizeof(dp[0])); dp[0][0] = 1; for(int i=1; i<=n; ++i) { ll sum = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2])%MOD; if(i<=m) dp[i][0] = sum; else if(i == m+1) dp[i][0] = (sum-1+MOD)%MOD; else dp[i][0] = ((sum - dp[i-m-1][1] - dp[i-m-1][2])%MOD+MOD)%MOD; if(i<=k) dp[i][1] = sum; else if(i == k+1) dp[i][1] = (sum-1+MOD)%MOD; else dp[i][1] = ((sum - dp[i-k-1][0] - dp[i-k-1][2])%MOD+MOD)%MOD; dp[i][2] = sum; } return (dp[n][0] + dp[n][1] + dp[n][2]) % MOD;}int main(){ while(cin >> n >> m >> k) cout << (f(n, k) - f(m-1, k) + MOD)%MOD << endl; return 0;}新聞熱點
疑難解答
