AcWing 2889. 再探石子合并
原题链接
中等
作者:
皓首不倦
,
2021-05-08 17:38:26
,
所有人可见
,
阅读 1129
/*
*
* dp(i, j)表示第i个石子到第j个石子的区间中所有石子合并的最小开销,最后求解答案是dp(0, n-1)
* 其中dp(i, j) = min { dp(i, k) + dp(k+1, j) + w(i, j) } (i <= k < j)
* w(i, j) 是石子权值的区间和,满足四边形不等式,因此整个DP可以用四边形不等式的性质进行优化
*
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 5005;
int dp[N][N];
int P[N][N]; // P[i][j]表示dp(i, j)的全局最优决策点, 用于四边形不等式优化
int S[N]; // 石子前缀和
int arr[N];
// w函数就是石子的前缀和
int w(int i, int j) {
return i == 0 ? S[j] : S[j] - S[i-1];
}
int main(void) {
//freopen("/Users/grh/Programming/CLionProjects/SimpleTest/input.txt", "r", stdin);
int n;
scanf("%d", &n);
int tot = 0;
for (int i = 0; i < n; i++) {
scanf("%d", arr + i);
tot += arr[i];
S[i] = tot;
}
for (int i = n-1; i >= 0; i--) {
P[i][i] = i;
dp[i][i] = 0;
for (int j = i+1; j < n; j++) {
dp[i][j] = 0x7fffffff;
for (int k = P[i][j-1]; k <= P[i+1][j]; k++) {
if (k >= i && k < j) {
int val = dp[i][k] + dp[k+1][j] + w(i, j); // k的枚举范围是[P(i, j-1), P(i+1, j)], 四边形不等式优化
if (val < dp[i][j]) {
P[i][j] = k;
dp[i][j] = val;
}
}
}
}
}
printf("%d\n", dp[0][n-1]);
return 0;
}