https://codeforces.com/gym/102428
首先,令 \(dp[i][j]\) 表示 最下层的有 \(i\) 块, 包括最下层总共还有 \(j\) 块的方案数
容易想到状态方程:$dp[i][j] = \sum_{k = 1} ^ i dp[k][j – i] * (i + 1 – k) $
然而是 \(O(n ^ 3)\) 的,会 T
此时改写上式:
$dp[i][j] = \sum_{k = 1} ^ i -k * dp[k][j – i] + \sum_{k = 1} ^ i (i + 1) * dp[k][j – i] $
现在可以用前缀和维护
注意给 \(dp\) 数组赋初值。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
int c, n;
ll dp[5005][5005];
ll pre[5005][5005], sum[5005][5005];
int main() {
scanf("%d%d", &c, &n);
for(int i = 1; i <= n; i++) dp[1][i] = 1, dp[i][i] = 1;
for(int j = 1; j <= n; j++) {
for(int i = 1; i <= c; i++) {
if(j < i) continue;
if(dp[i][j]) continue;
dp[i][j] = (dp[i][j] + 1ll * (i + 1) * pre[j - i][i] % mod) % mod;
dp[i][j] = (dp[i][j] - sum[j - i][i] + mod) % mod;
}
for(int i = 1; i <= c; i++) {
pre[j][i] = (pre[j][i - 1] + dp[i][j]) % mod;
sum[j][i] = (sum[j][i - 1] + 1ll * i * dp[i][j]) % mod;
}
}
printf("%lld\n", dp[c][n]);
system("pause");
return 0;
}
p.s. 可惜这题在考场上并不会做,按照本场 5 题的水平还不算好。
原文地址:http://www.cnblogs.com/re0acm/p/16799642.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性