输出共 2 行, 第 1 行为最小得分, 第 2 行为最大得分.
问题分析
N 个堆相邻, 每次选择相邻的两个合并, 就是对两两区间的选择, 典型的区间 dp 类型. 题目为环形, 环转为链最简单的方式就是用一个长度为环长度两倍的链来依次存环的数据两次. 现用较为简便的链形的模型来理顺以下区间 dp 的思路: dp 的关键就是找到状态的转移, 要找对状态的转移, 那么对状态的定义就很重要. 所以定义的状态要能够分解为更小的状态, 可以这样思考:
1)如何将状态分解为更小的子状态的.
2)子状态是否能够继续类似分解为更小的子状态.
3)终止状态是怎样.
4)终止状态在不断分解时是否能够最终达到.
根据以上的灵魂四问, 可以尝试这样来定义状态 f[i][j]= 区间 i 到 j 合并后的最大权值, 接下来验证一下. 对于 1:f[i][j] = max(f[i][k] + f[k][j] + w[i to j],f[i][j]),(i<=k<=j),i 到 j 合并的最大权值可以分解为两个子区间的最大合并的最大权值和再加上 i 到 j 的总权值 (就是把两个子区间合成当前状态的新获取的权值), 这个权值可以通过输入时记录前缀和来解决. 对于 2: 子状态 f[i][k],f[k][j] 仍然可以类似继续分解. 对于 3: 终止状态就是 i==j 的时候即区间只有一个的时候, 此时无法合并, 故得分为 0. 对于 4: 根据 1 2, 区间状态最终确实可以分解至区间长度为 1. 到这里已经可以基本确认状态的转移设定已经成功啦, 灵魂四问 nb~(来自我的数据结构老师).
接着来分析一下这种转移的大概复杂度, 环形, 所以区间的起点选择 n 次. 每次选完区间后开始 dp, 区间 dp 可以看作是对一个长度为 n 的区间, 从长度为 1 开始一直选择到 n, 没选定一个 ni 长度的区间, 还要选择 ni 次中间结点作为划分, 所以据此可以估计大致的时间复杂度为 n^3. 再看看题目的数据规模 100, 将环转为链长度最大为 200, 所以 n^3 是没有问题的. 再一次确认此状态转移可行.
状态的转移已经确定好聊, 接下来就是用递推还是用递归的问题啦. 递推是在递归逻辑掌握得非常透的时候的一种提高效率的转换, 弱弱我还是先从递归开始吧. 根据之前的灵魂四问, 递归的 dp 就很好写啦(记忆化就不再赘述了).
- // 以求最小值为例
- // 终止状态 l==r, 区间长度为 1. 对应四问的 3
- if(l == r) return 0;
- // 状态转移不断缩小, 对应四问的 1 2
- if(f1[l][r] == Inf) { // 尚未处理过
- for(int i=l; i<r; ++i) {
- f1[l][r] = min(f1[l][r],
- getMin(l, i) + getMin(i+1, r) + w[r]-w[l-1]);
- }
- }return f1[l][r];
关键的 dp 已经设计完成, 其他的输入输出细节就是代码的功底了, 上个完整代码.
- #include <cstdio>
- #include <iostream>
- #include <cstring>
- #define Inf 0x3f3f3f3f
- using namespace std;
- const int N = 202;
- int n, ans1, ans2;
- int f1[N*2][N*2], f2[N*2][N*2];
- int w[N*2];
- inline int min(const int& a, const int& b) { return a<b? a:b; }
- inline int max(const int& a, const int& b) { return a>b? a:b; }
- inline void __ini__() {
- scanf("%d", &n);
- memset(f1, Inf, sizeof(f1)); // 初始化记忆数组
- for(int i=0; i<2*N; ++i)
- for(int j=0; j<2*N; ++j)
- f2[i][j] = -Inf;
- for(int i=1; i<=n; ++i) {
- scanf("%d", w+i);
- w[n+i] = w[i]; // 利用双倍链代替环
- w[i] += w[i-1]; // 前缀求和
- }
- for(int i=n+1; i<=2*n; ++i) { // 增长部分的前缀和
- w[i] += w[i-1];
- }return;
- }
- int getMin(int l, int r) {
- if(l == r) return 0;
- if(f1[l][r] == Inf) { // 尚未处理过
- for(int i=l; i<r; ++i) {
- f1[l][r] = min(f1[l][r],
- getMin(l, i) + getMin(i+1, r) + w[r]-w[l-1]);
- }
- }return f1[l][r];
- }
- int getMax(int l, int r) {
- if(l == r) return 0;
- if(f2[l][r] == -Inf) {
- for(int i=l; i<r; ++i) {
- f2[l][r] = max(f2[l][r],
- getMax(l, i) + getMax(i+1, r) + w[r]-w[l-1]);
- }
- }return f2[l][r];
- }
- int main() {
- __ini__();
- ans1 = Inf, ans2 = -Inf;
- for(int s=1; s<=n; ++s) {
- ans1 = min(getMin(s, s+n-1), ans1);
- ans2 = max(getMax(s, s+n-1), ans2);
- }
- printf("%d\n%d\n", ans1, ans2);
- return 0;
- }
- full solution
嗯呐, 对于递归的方式基本上已经有所把握了吧. 接下来更进一步, 递推递推. 仍然基于以上的灵魂四问, 但与递归有点不同, 递推是从终止状态 (即可以确定的已知状态) 往更高一级的状态推导. 简而言之: 递归从求解状态索取结果直至可确定的状态, 递推从可确定的状态一直推导到求解状态.
- for(基状态: len=1 -> n) { // 基状态区间长度为 1 是确定的, 遍历到下一层 len=2 确定, then len=3 确定...
- for(在当前的区间长度下枚举区间: 起点 s=1 -> n) {
t = s + len-1; 区间的结尾
- for(中间划分结点: k=s -> t-1) {
- // 根据题意处理
- f[s][t] = min(f[s][t], f[s][k]+f[k+1][t]+w[s to t]);
- }
- }
- }
- // 递推的代码实现
- // 得到的 f[][]就是和递归方式得到的一样的状态
- for(int p=1;p<n;p++) {
- for(int i=1,j=i+p;(j<n+n) && (i<n+n);i++,j=i+p) {
- for(int k=i;k<j;k++) {
- f1[i][j] = max(f1[i][j], f1[i][k]+f1[k+1][j]+d(i,j));
- }
- }
- }
得到所有区间的可能状态之后就是简单的对答案枚举了, 这里就不再贴代码了.
谢谢观赏~
来源: http://www.bubuko.com/infodetail-3286780.html