acwing算法提高之动态规划--区间DP

1 基础知识

暂无。。。

2 模板

暂无。。。

3 工程化

题目1：环形石子合并。

解题思路：已知石子合并的求解方式，关键是如何化解环形。可以将两个相同数组拼起来，答案就是f[1][n], f[2][n+1], f[3][n+2], ..., f[n][2*n-1]中的最小值。

区间DP的状态的遍历模板为，

for (int len = 1; len <= n; ++len) {
	for (int l = 1; l + len - 1 <= 2 * n; ++l) {
		int r = l + len - 1;
		//进行状态计算操作...
	}
}

此处，状态定义f[i][j]：表示合并[i,j]石子的最小代价。

状态转移为：

f[i][j];
for (int k = i; k < j; ++k) {
	f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}

其中s[]表示前缀和数组。

C++代码如下，

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210;
int n;
int w[N * 2];
int s[N * 2];
int f[N * 2][N * 2]; //最小代价
int g[N * 2][N * 2]; //最大代价

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = n + 1; i <= 2 * n; ++i) w[i] = w[i - n];
    
    for (int i = 1; i <= 2 * n; ++i) s[i] = s[i - 1] + w[i];
    
    memset(f, 0x3f, sizeof f); //初始化
    memset(g, -0x3f, sizeof g); //初始化
    
    //状态计算
    for (int len = 1; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= 2 * n; ++l) {
            int r = l + len - 1;
            if (l == r) f[l][r] = g[l][r] = 0;
            else {
                for (int k = l; k < r; ++k) {
                    f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                    g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
                }
            }
        }
    }
    
    int maxv = -0x3f3f3f3f, minv = 0x3f3f3f3f;
    for (int i = 1; i <= n; ++i) {
        minv = min(minv, f[i][n + i - 1]);
        maxv = max(maxv, g[i][n + i - 1]);
    }
    
    cout << minv << endl << maxv << endl;
    
    return 0;
}

题目2：能量项链。

解题思路：主要就是把题目的意思理解好，解题方法同题目1。

C++代码如下，

#include <iostream>

using namespace std;

const int N = 210;

int n;
int w[N];
int f[N][N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
        w[i + n] = w[i];
    }
    
    //计算状态
    for (int len = 3; len <= n + 1; ++len) {
        for (int l = 1; l + len - 1 <= 2 * n; ++l) {
            int r = l + len - 1;
            for (int k = l + 1; k < r; ++k) {
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
            }
        }
    }
    
    int res = 0;
    for (int i = 1; i <= n; ++i) res = max(res, f[i][n + i]);
    cout << res << endl;
    
    return 0;
}

题目3：凸多边形的划分。

解题思路：区间DP，注意状态定义和转移时的细节。需要用到高精度计算。

C++代码如下（这里就不写高精度版本了，写个普通版本，高精度版本以后再补充），

#include <iostream>

using namespace std;

const int N = 60;
int n;
int w[N];
int f[N][N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    
    for (int len = 3; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            f[l][r] = 0x3f3f3f3f;
            for (int k = l + 1; k < r; ++k) {
                f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
            }
        }
    }
    
    cout << f[1][n] << endl;
    
    return 0;
}

题目4：