1 条题解
-
0
[N] Slimes(dp_n)题解
题意简述
只史莱姆排一列,大小 。每次合并相邻两只,代价为新大小,求合并成一体的最小总代价。
思路
状态
设 = 把区间 合并成一只史莱姆的最小代价。
转移
最后一次合并必是把 与 合并()。合并后大小是区间和 ,而两个子区间各自的内部代价是 :
$$f_{l,r} = \min_{l \le m < r}\left( f_{l,m} + f_{m+1,r} \right) + S(l,r),$$, 用前缀和 求。
为什么正确
任何合并方案都对应一棵"合并二叉树",其最后一次合并一定把序列切成左右两段——这正对应了枚举 的所有情形,且左右两段独立最优(最优子结构)。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <algorithm> using namespace std; static long long pre[405], f[405][405]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { long long a; scanf("%lld", &a); pre[i] = pre[i - 1] + a; } for (int len = 2; len <= n; len++) for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; long long best = (1LL << 62); for (int m = l; m < r; m++) best = min(best, f[l][m] + f[m + 1][r]); f[l][r] = best + pre[r] - pre[l - 1]; } printf("%lld\n", f[1][n]); return 0; }易错点
- 代价是"合并后的和",所以要加 ,不是 。
- 长度从 开始枚举( 已初始)。
best初值要足够大(用1LL<<62),别用INT_MAX。- 级别的 累加后代价可达 ,必须
long long。
数据说明
共 17 组:4 组官方样例(含 ); 的相同与最大值; 全相同与 ; 随机; 随机; 全 、递增、小值随机、 两值随机,覆盖最坏复杂度与溢出。
- 1
信息
- ID
- 23
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者