大意: $n$ 个城市, $m$ 种核电站, 第 $i$ 种假设要建在第 $x$ 个城市, 必须满足 $[x-i,x+i]$ 范围内无其他核电站, 求建核电站的方案数.
简单 $dp$ 题, 设 $dp[i][j]$ 为位置 $i$ 建第 $j$ 种核电站的方案数.
枚举上一个核电站的位置来转移, 有:
- $dp[i][1]=1+dp[i-2][1]+\sum\limits_{
- k=1
- }^2 dp[i-3][k]+\sum\limits_{
- k=1
- }^3dp[i-4][k]+...$
- $dp[i][j]=dp[i][j-1]-\sum\limits_{
- k=1
- }^{
- j-1
- }dp[i-j][k],\space j>1$.
前缀优化一下即可 $O(nm)$.
- #include <iostream>
- #include <cstdio>
- #define REP(i,a,n) for(int i=a;i<=n;++i)
- #define PER(i,a,n) for(int i=n;i>=a;--i)
- using namespace std;
- const int P = 1e9+7;
- int dp[10010][110], s[10010];
- int main() {
- int t;
- scanf("%d", &t);
- REP(cas,1,t) {
- int n, m;
- scanf("%d%d", &n, &m);
- REP(i,1,n) {
- int now = 1;
- dp[i][1] = 1;
- PER(j,1,i-2) {
- if (now==m) {
- (dp[i][1] += s[j]) %= P;
- break;
- }
- (dp[i][1] += dp[j][now++]) %= P;
- }
- REP(j,2,m) dp[i][j] = (dp[i][j-1]-(i-j>0?dp[i-j][j-1]:0))%P;
- REP(j,2,m) (dp[i][j] += dp[i][j-1]) %= P;
- s[i] = (s[i-1]+dp[i][m])%P;
- }
- int ans = (s[n]+1)%P;
- if (ans<0) ans += P;
- printf("Case %d: %d\n", cas, ans);
- }
- }
来源: http://www.bubuko.com/infodetail-3110615.html