记录
22:01 2024-2-10
http://poj.org/problem?id=1179
区间DP问题。区间DP问题可能需要注意的点就是是根据区间长度来计算的，随着迭代区间长度不断增加，结果也就计算出来了
这种“任意选择一个位置断开， 复制形成2倍长度的链” 的方法，是解决DP中环形结构的常用手段之一
因此读入数据选择了断开第一条边然后复制成2倍长度的链，这样就把问题变成了非环问题，通过区间DP计算出结果
注意这里使用的是\(oper[k+1]\)
\[dp\_max[l][r] = \begin{cases} \max_{l \le k < r}{ \max \begin{cases} dp\_max[l][k] \quad oper \quad dp\_max[k+1][r] \\ dp\_min[l][k] \quad * \quad dp\_min[k+1][r] \\ dp\_max[l][k] \quad * \quad dp\_min[k+1][r] \\ dp\_min[l][k] \quad * \quad dp\_max[k+1][r] \\ \end{cases} } \end{cases} \]\[dp\_min[l][r] = \begin{cases} \min_{l \le k < r}{ \min \begin{cases} dp\_min[l][k] \quad oper \quad dp\_min[k+1][r] \\ dp\_max[l][k] \quad * \quad dp\_max[k+1][r] \\ dp\_max[l][k] \quad * \quad dp\_min[k+1][r] \\ dp\_min[l][k] \quad * \quad dp\_max[k+1][r] \\ \end{cases} } \end{cases} \]点击查看代码
#include<iostream>
#include<vector>
#include<stdio.h>
#include<string.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 55;
int value[MAXN * 2], dp_max[MAXN * 2][MAXN * 2], dp_min[MAXN * 2][MAXN * 2];
char oper[MAXN * 2];
int main() {
// 0xcf 11001111 ~x + 1 = 00110001 值为 -31
// 0x3f 00111111
// -0x3f 11000001 0xc1
memset(dp_max, 0xcf, sizeof(dp_max));
memset(dp_min, 0x3f, sizeof(dp_min));
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> oper[i] >> value[i];
oper[i + n] = oper[i];
value[i + n] = value[i];
}
for(int i = 1; i <= 2 * n; i++) dp_max[i][i] = dp_min[i][i] = value[i];
for(int len = 2; len <= n; len++) {
for(int l = 1; l + len - 1 <= n * 2 ; l++) {
int r = l + len - 1;
for(int k = l; k < r; k++) {
// [l,k] oper[k + 1] [k,r]
if(oper[k + 1] == 't') {
dp_max[l][r] = max(dp_max[l][r], dp_max[l][k] + dp_max[k+1][r]);
dp_min[l][r] = min(dp_min[l][r], dp_min[l][k] + dp_min[k+1][r]);
} else {
dp_max[l][r] = max(dp_max[l][r], dp_max[l][k] * dp_max[k+1][r]);
dp_max[l][r] = max(dp_max[l][r], dp_min[l][k] * dp_min[k+1][r]);
dp_max[l][r] = max(dp_max[l][r], dp_max[l][k] * dp_min[k+1][r]);
dp_max[l][r] = max(dp_max[l][r], dp_min[l][k] * dp_max[k+1][r]);
dp_min[l][r] = min(dp_min[l][r], dp_min[l][k] * dp_min[k+1][r]);
dp_min[l][r] = min(dp_min[l][r], dp_max[l][k] * dp_max[k+1][r]);
dp_min[l][r] = min(dp_min[l][r], dp_max[l][k] * dp_min[k+1][r]);
dp_min[l][r] = min(dp_min[l][r], dp_min[l][k] * dp_max[k+1][r]);
}
}
}
}
int result = -INF;
for(int i = 1; i <= n; i++) {
if(dp_max[i][i+n-1] > result) {
result = dp_max[i][i+n-1];
}
}
cout << result << endl;
for(int i = 1; i <= n; i++) {
if(dp_max[i][i+n-1] == result)
cout << i << " ";
}
}