M_sea

洛谷4342 [IOI1998]Polygon
Luogu算法对于这种环形+区间问题,考虑区间DP。首先肯定要破环为链。考虑没有负数的做法。那么这题和石子合并是类...
扫描右侧二维码阅读全文
30
2018/08

洛谷4342 [IOI1998]Polygon

Luogu

算法

对于这种环形+区间问题,考虑区间DP。

首先肯定要破环为链。

考虑没有负数的做法。那么这题和石子合并是类似的。

但是这里有了负数,而且负数乘负数还等于正数。

所以我们除了设$f[i][j]$表示区间最大之外,还要设$g[i][j]$表示区间最小。

那么转移方程很容易得出。

最后答案即为$\max_{i=1}^{n}f[i][i+n-1]$。

得出答案后,再输出所有$f[i][i+n-1]=ans$的$i$即可。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline void chmax(int& a,int b) { if (b>a) a=b; }
inline void chmin(int& a,int b) { if (b<a) a=b; }

int n;
char op[110];
int a[110];
int f[110][110]; //f[i][j]表示i到j的最大值 
int g[110][110]; //g[i][j]表示i到j的最小值 

int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for (re int i=1;i<=n;i++) {
        cin>>op[i]>>a[i];
        op[i+n]=op[i],a[i+n]=a[i];
    }
    n<<=1;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++) {
            if (i==j) f[i][j]=g[i][j]=a[i];
            else f[i][j]=-32769,g[i][j]=32768;
        }
    for (re int l=2;l<=(n>>1);l++)
        for (re int i=1;i+l-1<=n;i++) {
            int j=i+l-1;
            for (re int k=i;k<j;k++) {
                if (op[k+1]=='x') {
                    chmax(f[i][j],f[i][k]*f[k+1][j]);
                    chmax(f[i][j],g[i][k]*g[k+1][j]);
                    chmin(g[i][j],f[i][k]*g[k+1][j]);
                    chmin(g[i][j],g[i][k]*f[k+1][j]);
                    chmax(f[i][j],g[i][k]*g[k+1][j]);
                }
                else {
                    chmax(f[i][j],f[i][k]+f[k+1][j]);
                    chmin(g[i][j],g[i][k]+g[k+1][j]);
                }
            }
        }
    n>>=1; int ans=-2147483647;
    for (re int i=1;i<=n;i++)
        if (f[i][i+n-1]>ans) ans=f[i][i+n-1];
    printf("%d\n",ans);
    for (re int i=1;i<=n;i++)
        if (f[i][i+n-1]==ans) printf("%d ",i);
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 58 PM

3 条评论

  1. !Wzz

    不用chmin(g[i][j],g[i][k]*g[k+1][j]);吗?

    1. M_sea
      @!Wzz

      不知道为什么不加能过,可能是数据太氵了

    2. M_sea
      @!Wzz

      好像要加诶qwq
      我改一下qwq

发表评论