浅说区间dp（下）

文章目录

• 环形区间dp
• 例题
• [NOI1995] 石子合并
• • 题目描述
  • 输入格式
  • 输出格式
  • 样例 #1
  • • 样例输入 #1
    • 样例输出 #1
  • 提示
  • 思路
• [NOIP2006 提高组] 能量项链
• • 题目描述
  • 输入格式
  • 输出格式
  • 样例 #1
  • • 样例输入 #1
    • 样例输出 #1
  • 提示
  • 思路
• [NOIP2001 提高组] 数的划分
• • 题目描述
  • 输入格式
  • 输出格式
  • 样例 #1
  • • 样例输入 #1
    • 样例输出 #1
  • 提示
  • 思路
• 放苹果
• • 题目描述
  • 输入格式
  • 输出格式
  • 样例 #1
  • • 样例输入 #1
    • 样例输出 #1
  • 样例 #2
  • • 样例输入 #2
    • 样例输出 #2
  • 提示
  • 思路
• 总结

环形区间dp

上一讲我们主要是讲解的链式的区间dp，但是我们经常会遇见一个环的dp问题，那么我们这时候应该怎么办呢，我们还是以一个生活例子来引入
又是wjq~~
wjq又要开始合并衣服了，最近的wjq中了邪，喜欢圆圆的东西，所以这一次她把衣服放成了一个圆圈，总计有 N 件衣服，每件衣服有一个遮挡程度，现要将衣服有次序地合并成一堆，规定每次只能选相邻的 2 件合并成新的一堆，并将新的一堆的遮挡程度，记为该次合并的得分。
首先我们不难想到，每一件衣服都有可能是起点，所以我们现在就有以下几种情况：

假设现在圆圈里有“黑丝”，“白丝”，“泳装”，“jk”
那么我们就有：
“黑丝”，“白丝”，“泳装”，“jk”
“白丝”，“泳装”，“jk”，“黑丝”
“泳装”，“jk”，“黑丝”，“白丝”
“泳装”，“jk”，“黑丝”，“白丝”
总计四种情况

如果我们去找起点的话，太过繁琐了，那么我们来想想怎么优化。不难发现，当我们求解“黑丝”，“白丝”，“泳装”，“jk”时，“白丝”，“泳装”，“jk”，已经有了答案，那么我们在计算“白丝”，“泳装”，“jk”，“黑丝”的时候，就不用再次计算“白丝”，“泳装”，“jk”了，所以我们这里可以将整个数组copy一遍，放到后面，这样我们就可以避免重复计算了
这样无论哪个点为起点，再向后面枚举3个点都是一个完整的区间，即区间[i,i+n-1]为一个完整的区间。环变链后再做一次和前面一样的dp，注意下范围和边界，最后因为所有的长度为n的区间都有可能是答案，所以答案在min(dp[i,i+n-1])中。
要注意i要枚举到n的后面，因为后面的dp会用到这些值
这一招叫做化环为链，长度翻倍，是区间dp问题中常见的处理手段

---

例题

[NOI1995] 石子合并

题目描述

在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 $N$ 堆石子合并成 $1$ 堆的最小得分和最大得分。

输入格式

数据的第 $1$ 行是正整数 $N$，表示有 $N$ 堆石子。

第 $2$ 行有 $N$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 堆石子的个数。

输出格式

输出共 $2$ 行，第 $1$ 行为最小得分，第 $2$ 行为最大得分。

样例 #1

样例输入 #1

4
4 5 9 4

样例输出 #1

43
54

提示

$1\le N\le 100$，$0\le a_i\le 20$。

思路

这道题其实和上面的引入大同小异，可以直接套用

#include <iostream>
using namespace std;
const int N = 300;
const int INF = 10e9;
int n, dp[N][N], dp2[N][N];
int sum[N], s[N];

int main(){
	cin >> n;
	for (int i = 1; i <= n; i++) {
 	   cin >> s[i];
 	   s[i + n] = s[i];
	}
	for(int i = 1; i <= n * 2; i++){
		sum[i] = s[i] + sum[i - 1];
  	}
    for(int len = 1; len < n; len++){
   		for (int i = 1; i <= (n * 2 - len); i++){
      		int j = i + len;
        	dp[i][j] = INF;
        	for(int k = i; k < j; k++){
        		dp[i][j] = min (dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
       			dp2[i][j] = max (dp2[i][j], dp2[i][k] + dp2[k + 1][j] + sum[j] - sum[i - 1]);
       		}
        }
    }
    int ans = INF, ans2 = 0;
    for(int i = 1; i <= n; i++){
    	ans = min(ans, dp[i][i + n - 1]);
    	ans2 = max(ans2,dp2[i][i + n - 1]);
	}
    cout << ans << endl << ans2;
}

---

[NOIP2006 提高组] 能量项链

题目描述

在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有 $N$ 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 $m$，尾标记为 $r$，后一颗能量珠的头标记为 $r$，尾标记为 $n$，则聚合后释放的能量为 $m\times r\times n$（Mars 单位），新产生的珠子的头标记为 $m$，尾标记为 $n$。

需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设 $N=4$，$4$ 颗珠子的头标记与尾标记依次为 $(2,3)(3,5)(5,10)(10,2)$。我们用记号 $\oplus$ 表示两颗珠子的聚合操作，$(j\oplus k)$ 表示第 $j,k$ 两颗珠子聚合后所释放的能量。则第 $4$，$1$ 两颗珠子聚合后释放的能量为：

$(4\oplus 1)=10\times 2\times 3=60$。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为：

$(((4\oplus 1)\oplus 2)\oplus 3)=10\times 2\times 3+10\times 3\times 5+10\times 5\times 10=710$。

输入格式

第一行是一个正整数 $N$（$4\le N\le 100$），表示项链上珠子的个数。第二行是 $N$ 个用空格隔开的正整数，所有的数均不超过 $1000$。第 $i$ 个数为第 $i$ 颗珠子的头标记（$1\le i\le N$），当 $i<N$ 时，第 $i$ 颗珠子的尾标记应该等于第 $i+1$ 颗珠子的头标记。第 $N$ 颗珠子的尾标记应该等于第 $1$ 颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出格式

一个正整数 $E$（$E\le 2.1\times 10^9$），为一个最优聚合顺序所释放的总能量。

样例 #1

样例输入 #1

4
2 3 5 10

样例输出 #1

710

提示

NOIP 2006 提高组 第一题

思路

该题和合并石子(环)在处理方式上一样，都是通过把小区间合并成大区间，枚举合并两个区间的中间节点，计算出整个区间合并的最大能量因为也是一个环，所以我们还是先把环拆链，长度加倍，注意枚举顺序，因为是把小区间合并成大区间，所以先枚举区间长度，再枚举区间左端点，计算出区间右端点，最后再枚举最后一次合并的点，也就是断点，再计算答案。还是和前面一样，注意边界问题，区间长度不能大于n，也不能小于1.左右端点的范围不能小于或者大于真实情况。

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 301;

int dp[MAX_N][MAX_N];
int a[MAX_N];
int maxn=INT_MIN;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[n+i]=a[i];
    }
    for (int len = 1; len <= 2*n; ++len) {
        for (int i = 1; i + len - 1 <= 2*n; ++i) {
            int j = i + len - 1;
            for (int k = i+1; k < j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + a[i]*a[k]*a[j]);
            }
        }
    }
	for (int i=1;i<=n;i++){
		maxn=max(dp[i][i+n],maxn);
	}
    cout << maxn ;

    return 0;
}

---

[NOIP2001 提高组] 数的划分

题目描述

将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：$n=7$，$k=3$，下面三种分法被认为是相同的。

$1,1,5$;
$1,5,1$;
$5,1,1$.

问有多少种不同的分法。

输入格式

$n,k$ （$6<$