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;
}