2024，1，26
今天做石子合并的题比较多
贴一个模板
for (int len = 2; len <= n; len++) {
for (int i = 1， j; (j = i + len - 1) <= n; i++) {
for (int k = i; k < j; k++) {
if(dp[i][j] > dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1]) {
dp[i][j] = dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1];
}
}
}
}
uva10954
题意：
把n个数相加，把中间所得的结果相加，求这个结果的最小值。
思路：
这题一眼看上去是模拟，但是仔细一想，是个小根堆。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(int n) {
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 0, t; i < n; i++) {
cin >> t;
q.push(t);
}
int res = 0;
while(q.size() > 1) {
int a = q.top();
q.pop();
int b = q.top();
q.pop();
q.push(a + b);
res += a + b;
}
cout << res << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
while(1) {
int n;
cin >> n;
if(n) {
solve(n);
}
else {
break;
}
}
return 0;
}
uva10003
题意：
把线段切开，让代价最小。
思路：
起初我是把这个题和上面的那个题联系起来，以为就是逆向做，把小线段合并成一个大线段就行，但是不行。
想了很久，才想明白，上面那个题没有要求哪两个个数可以相加，但是对于这个题来说切线段和组合线段是相对的，所以必须是相邻的线段组合。
我看了题解是四边形不等式优化dp 类似的洛谷题是石子合并，当然有两个弱化版本，可以用三位循环dp求解，我先做这两个题然后学优化，最后来做这个题。
洛谷P1775 石子合并（弱化版）
题意：
N(N≤300)要将 N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。
思路：
N很小，考虑三重循环dp。
但是有一点小曲折：前缀和还是很好想的，通过前缀和进行区间的寻找，然后dp得到了下面代码：
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
for (int k = i; k < j; k++) {
if(dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1] < dp[i][j]) {
dp[i][j] = dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1];
}
}
}
}
看起来没有问题，但是得不出样例，看了题解之后才明白，要从小区间开始dp
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
vector<int>pre(n + 1);
vector dp(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = 1e18;
}
}
for (int i = 1; i <= n; i++) {
cin >> pre[i];
pre[i] += pre[i - 1];
dp[i][i] = 0;
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
if(dp[i][j] > dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1]) {
dp[i][j] = dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1];
}
}
}
}
cout << dp[1][n] << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
while(T--) {
solve();
}
return 0;
}
这个dp的实质就是大区间枚举拆分成两个小区间，通过遍历分割点找到最优解。
P1880 [NOI1995] 石子合并
（样例想了半天）这个题和上个石子合并的差别就在于把一段变成了环形，环形的话要考虑第一个和最后一个是相邻的，我按照套路开了两倍大小三维循环dp AC了。
但是比较曲折（可能好久不写题了），初始化的部分调了很久。
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
vector<int>pre(2 * n + 1);
vector dp(2 * n + 1, vector<int>(2 * n + 1));
vector dp2(2 * n + 1, vector<int>(2 * n + 1));
for (int i = 1; i <= 2 * n; i++) {
for (int j = 1; j <= 2 * n; j++) {
dp[i][j] = 1e18;
dp2[i][j] = -1;
}
}
for (int i = 1; i <= n; i++) {
cin >> pre[i];
pre[i + n] = pre[i];
pre[i] += pre[i - 1];
}
for (int i = 1; i <= 2 * n; i++) {
dp[i][i] = 0;
dp2[i][i] = 0;
}
for (int i = n + 1; i <= 2 * n; i++) {
pre[i] += pre[i - 1];
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= 2 * n; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
if(dp[i][j] > dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1]) {
dp[i][j] = dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1];
}
if(dp2[i][j] < dp2[i][k] + dp2[k + 1][j] + pre[j] - pre[i - 1]) {
dp2[i][j] = dp2[i][k] + dp2[k + 1][j] + pre[j] - pre[i - 1];
}
}
}
}
int minm = 1e18, maxm = -1;
for (int i = 1; i <= n + 1; i++) {
minm = min(minm, dp[i][i + n - 1]);
maxm = max(maxm, dp2[i][i + n - 1]);
}
cout << minm << endl << maxm << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
uva10003
做了上面两个题我发现其实不需要优化，这个题的复杂度$n\le50$ 就算是三重循环的区间dp也可以解决。
注意格式
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(int len) {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
int la = 0;
vector<int>vv;
for (auto it : v) {
vv.push_back(it - la);
la = it;
}
vv.push_back(len - la);
vector<int>pre(n + 2);
for (int i = 0; i < n + 1; i++) {
pre[i + 1] = pre[i] + vv[i];
}
n++;
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(i != j) {
dp[i][j] = 1e18;
}
else {
dp[i][j] = 0;
}
}
}
for (int len = 2; len <= n; len++) {
for (int i = 1, j; (j = i + len - 1) <= n; i++) {
for (int k = i; k < j; k++) {
if(dp[i][j] > dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1]) {
dp[i][j] = dp[i][k] + dp[k + 1][j] + pre[j] - pre[i - 1];
}
}
}
}
cout << "The minimum cutting is " << dp[1][n] << ".\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
while(1) {
int len;
cin >> len;
// cerr << len << "**\n";
if(len) {
solve(len);
}
else {
break;
}
}
return 0;
}