题目链接：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;}新闻热点
疑难解答
