寒假训练2024/1/26
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;
}
热门相关:重生隐婚:Hi,高冷权少! 唐土万里 顺明 顺明 抗日之全能兵王