题解 P4342 【[IOI1998]Polygon】
command_block
2018-10-01 23:18:43
### 总感觉这道题和[P1063 能量项链](https://www.luogu.org/problemnew/show/P1063)区别不大?
~~我就是仗着代码短来发题解的~~
这题怎么会是紫题呢?
思路楼下讲得很清楚,我就不赘述了……
```cpp
#include<iostream>
#include<cstring>
using namespace std;
long long n,tmp,f[105][105],ff[105][105],s[105],ans;
//ff表示区间最小值,f表示区间最大值
char op[105];
//没用区间DP的板子,所以有点慢(western reporter?)
void dfs(int i,int j)
{
if (f[i][j]>=0)return ;
for (int k=i+1;k<=j;k++){
dfs(i,k-1);dfs(k,j);
long long rf=f[k][j],rff=ff[k][j],lf=f[i][k-1],lff=ff[i][k-1];
f[i][j]=max(f[i][j],op[k]=='t' ? lf+rf:max(lf*rf,lff*rff));
ff[i][j]=min(ff[i][j],op[k]=='t' ? lff+rff:min(min(lff*rf,lf*rff),lff*rff));
//方程一点也不长,而且很好理解
}
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++){
cin>>op[i]>>s[i];
s[i+n]=s[i];
op[i+n]=op[i];
//拆环为链
}memset(f,-0x3f,sizeof(f));
memset(ff,0x3f,sizeof(ff));
ans=-1ll<<60;
for (int i=1;i<=n;i++)
ff[i][i]=ff[i+n][i+n]=f[i][i]=f[i+n][i+n]=s[i];
//边界条件
for (int i=1;i<=n;i++){
dfs(i,i+n-1);
ans=max(ans,f[i][i+n-1]);
}cout<<ans<<endl;
for (int i=1;i<=n;i++)
if (ans==f[i][i+n-1])cout<<i<<' ';
return 0;
}
```
~~皮这一下很开心~~
我是在[夏令营梗收集帖](https://www.luogu.org/discuss/show/51862?&page=11)见到这题的……