拆环成链
O(n^3)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
// Tag: 区间DP 环形问题
/*
对于 环形问题 我们常用的方法就是 拆环成链
把环形数据 从某一起点开始 复制成两倍长度的链 即可实现。
本题目要求得出进行N次操作之后,分数的最大值。
初次做这道题的时候可能会怀疑 这个问题 是否满足最优子结构?
如果仅仅记录某一区间中的最大值,显然是无法做出正确的状态转移的。
所以:
状态表示:
f[ l , r , 0 ] 代表 区间 l,r 合成一个点之后,顶点上的数值最大是多少。
f[ l , r , 1 ] 代表 区间 l,r 合成一个点之后,顶点上的数值最小是多少。
则可得状态转移方程如下:
f[l,r,0] = max( f[l,k,0] + \ * f[k+1,r,0] , f[l,k,p] * f[k+1,r,q] (p,q∈{0,1}) ]
即,最大值只能来自于三个数值:
1. 两个最大值相加、乘
2. 两个最小值相乘
3. 一个最大值、一个最小值相乘 (当一个区间的最大、最小值均负,而另一个区间的最大、最小值均正)
同理,
f[l,r,1] = min( f[l,k,1] + \ * f[k+1,r,1] , f[l,k,p] * f[k+1,r,q] (p,q∈{0,1}) ]
因为要表示的两个状态 都能 由本区间内长度更小的 状态转移过来。
而且 这两个状态的计算 不会相互依赖。
所以,这道题不会产生后效性。
*/
const int N=110,INF = 32768;
int n;
int w[N];
char c[N];
int f[N][N], g[N][N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>c[i]>>w[i];
c[i+n] = c[i];
w[i+n] = w[i];
}
for(int len=1;len<=n;len++)
{
for(int l=1;l+len-1<=n*2;l++)
{
int r = l+len-1;
if(len==1) f[l][r] = g[l][r] = w[l];
else
{
f[l][r] = -INF, g[l][r] = INF;
for(int k=l;k<r;k++) //枚举从那个开始合成
{
char op = c[k+1];
int minl = g[l][k], minr = g[k+1][r];
int maxl = f[l][k], maxr = f[k+1][r];
if(op == 't')
{
f[l][r] = max(f[l][r],f[l][k]+f[k+1][r]);
g[l][r] = min(g[l][r],g[l][k]+g[k+1][r]);
}
else
{
int x1 = maxl * maxr, x2 = minl * minr, x3 = maxl * minr, x4 = minl * maxr;
f[l][r] = max(f[l][r],max(max(x1,x2),max(x3,x4)));
g[l][r] = min(g[l][r],min(min(x1,x2),min(x3,x4)));
}
}
}
}
}
int res = -INF;
for(int i=1;i<=n;i++) res = max(res, f[i][i+n-1]);
cout<<res<<endl;
//c[i+1] 是 w[i] 和 w[i+1] 进行的操作。
for(int i=1;i<=n;i++)
{
if(res == f[i][i+n-1])
cout<<i<<" ";
}
return 0;
}