DP中环形处理
对于DP中存在环的情况，大致有两种处理的方法：
- 对于很多的区间DP来说，很常见的方法就是把原来的环从任意两点断开（注意并不是直接删掉这条边），在复制一条一模一样的链在这条链的后方，当做线性问题来解，即可实现时间复杂度降维。
- 情况一：将原来的环从任意两点断开，再当做线性问题来解。情况二：添加一些特殊条件，将断开的前后强行连接起来。两种情况取其中的最优解即可。亦可以实现时间复杂度的降维。
本篇博客将对于第一种情况进行分析。
根据一道例题来探讨。
题目链接：
POJ 1179 Polygon
Description
Polygon is a game for one player that starts on a polygon with N vertices, like the one in Figure 1, where N=4. Each vertex is labelled with an integer and each edge is labelled with either the symbol + (addition) or the symbol * (product). The edges are numbered from 1 to N.
On the first move, one of the edges is removed. Subsequent moves involve the following steps:
�pick an edge E and the two vertices V1 and V2 that are linked by E; and
�replace them by a new vertex, labelled with the result of performing the operation indicated in E on the labels of V1 and V2.
The game ends when there are no more edges, and its score is the label of the single vertex remaining.
Consider the polygon of Figure 1. The player started by removing edge 3. After that, the player picked edge 1, then edge 4, and, finally, edge 2. The score is 0.
Write a program that, given a polygon, computes the highest possible score and lists all the edges that, if removed on the first move, can lead to a game with that score.
Input
Your program is to read from standard input. The input describes a polygon with N vertices. It contains two lines. On the first line is the number N. The second line contains the labels of edges 1, ..., N, interleaved with the vertices' labels (first that of the vertex between edges 1 and 2, then that of the vertex between edges 2 and 3, and so on, until that of the vertex between edges N and 1), all separated by one space. An edge label is either the letter t (representing +) or the letter x (representing *).
3 <= N <= 50
For any sequence of moves, vertex labels are in the range [-32768,32767].
Output
Your program is to write to standard output. On the first line your program must write the highest score one can get for the input polygon. On the second line it must write the list of all edges that, if removed on the first move, can lead to a game with that score. Edges must be written in increasing order, separated by one space.
Sample Input
4
t -7 t 4 x 2 x 5
Sample Output
33
1 2
Source
IOI 1998
分析
题目大意
给出一个多边形，删除一条边，合并剩下的点（若边的符号为x，则进行乘法；若边的符号为t，则进行加法）。问操作后剩下的点的值最大为多少。
样例简单解释
删除第1或第2条边，按照上述题意依此合并4，3，2或4，3，1，所以是\(5×2×4+(-7)\)
首先来考虑是一条链的情况
对于一个区间 \([l,r]\) 中，可以找到一个点 \(k\) \((k∈[l, r))\) ，通过合并区间 \([l,k]\) 与区间 \([k+1,r]\) 来更新区间\([l,r]\)的状态。
具体是什么状态？定义一个区间最大值与一个区间最小值。即定义 \(dp[i][j][0|1]\)来表示区间 \([l,j]\) 的最值。其中，0为最大值，1为最小值。
为何需要最小值？因为该数据中存在负数，负负得正，很有可能两个区间的最小值都为负数，他们的乘积远远大于这两个区间的最大值的乘积。
需要讨论两种情况
- \(1\) 当两点之间为加号时。对于每一个k，都只能用两区间的最大值之和来更新合并区间的最大值，最小值同理。不可能用最大值与最小值之和来更新区间最值。
- \(2\) 当两点之间为加号时。对于每一个k，用四种不同的搭配，考虑到不同正负的情况，来更新区间的最值：
\(dp[l][k][1] * dp[k + 1][r][1]\)
\(dp[l][k][0] * dp[k + 1][r][0]\)
\(dp[l][k][1] * dp[k + 1][r][0]\)
\(dp[l][k][0] * dp[k + 1][r][1]\)
若枚举删除每一条边，每次都来跑一遍DP，则时间复杂度为 \(O(n^4)\)。但本题数据不强，若规定 \(n≤100\)，则必定会超时。
按照在复制一条一模一样的链在这条链的后方，当做线性问题来解这样来处理，则会将时间复杂度降到\(O(n^3)\)。
拿样例来举例：
原图：
化成一条链后：
在这条链上，\(dp[1][4]\) 就可以理解为删除边3后的最大值
同理，\(dp[2][5]\) 就可以理解为删除边2后的最大值
\(dp[3][6]\) 就可以理解为删除边1后的最大值
\(dp[4][7]\) 就可以理解为删除边4后的最大值
所以最大值就可以表示为 \(Max(dp(i,i+n-1))\)
这样就省略了很多重复的计算。
C++实现
#include <cstdio>
#define INF 0x3f3f3f3f
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
void Quick_Read(int &N) {
N = 0;
char c = getchar();
int op = 1;
while(c < '0' || c > '9') {
if(c == '-')
op = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
N = (N << 1) + (N << 3) + c - 48;
c = getchar();
}
N *= op;
}
const int MAXN = 105;
int dp[MAXN][MAXN][2];
int A[MAXN];
bool F[MAXN];
int n;
int ans = -INF;
void DP() {
for(int i = 1; i <= n; i++) {
A[i + n] = A[i];
F[i + n] = F[i];
}
n <<= 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
dp[i][j][0] = -INF;
dp[i][j][1] = INF;
}
for(int i = 1; i <= n; i++)
dp[i][i][1] = dp[i][i][0] = A[i];
for(int len = 2; len <= n; len++) {
for(int l = 1; l <= n - len + 1; l++) {
int r = l + len - 1;
for(int k = l; k < r; k++) {
if(F[k + 1]) {
for(int p = 0; p <= 1; p++)
for(int q = 0; q <= 1; q++) {
dp[l][r][0] = Max(dp[l][r][0], dp[l][k][p] * dp[k + 1][r][q]);
dp[l][r][1] = Min(dp[l][r][1], dp[l][k][p] * dp[k + 1][r][q]);
}
}
else {
dp[l][r][0] = Max(dp[l][r][0], dp[l][k][0] + dp[k + 1][r][0]);
dp[l][r][1] = Min(dp[l][r][1], dp[l][k][1] + dp[k + 1][r][1]);
}
}
}
}
for(int i = 1; i <= n; i++)
ans = Max(ans, dp[i][i + (n >> 1) - 1][0]);
printf("%d\n", ans);
for(int i = 1; i <= (n >> 1); i++)
if(dp[i][i + (n >> 1) - 1][0] == ans)
printf("%d ", i);
}
void Read() {
Quick_Read(n);
char c = getchar();
for(int i = 1; i <= n; i++) {
while(c != 't' && c != 'x')
c = getchar();
if(c == 'x')
F[i] = true;
Quick_Read(A[i]);
c = -1;
}
}
int main() {
Read();
DP();
return 0;
}