[IOI1998]Polygon

倍长环为链

考虑负负得正,定义 表示合并 的最大值, 表示合并 后的最小值

按要求转移即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=102;

int n;
int a[N*2],op[N*2];
int f[N*2][N*2];//f[i,j] 把 [i,j] 合并后的最高分数
int g[N*2][N*2];//g[i,j] 把 [i,j] 合并后的最低分数
int ans=0,p[N*2],cnt;

signed main(){cin>>n;//scanf("%lld",&n);
    memset(g,0x3f,sizeof(g));
    memset(f,0xc0,sizeof(f));
    for(int i=1;i<=n;i++){char opr[5];
        cin>>opr>>a[i];//scanf("%s %lld",opr,&a[i]);
        if(opr[0]=='x')op[i]=1;//0 +;1 *
        a[i+n]=a[i],op[i+n]=op[i];
        f[i][i]=g[i][i]=f[i+n][i+n]=g[i+n][i+n]=a[i];//init
    }
    for(int i=1;i<n;i++){// 枚举区间长度
        for(int j=1;j+i<=n*2;j++){// 枚举开头
            //[j,j+i]
            for(int k=j+1;k<=j+i;k++){if(op[k]==0){f[j][j+i]=max(f[j][j+i],f[j][k-1]+f[k][j+i]);
                    g[j][j+i]=min(g[j][j+i],g[j][k-1]+g[k][j+i]);
                }
                if(op[k]==1){f[j][j+i]=max(f[j][j+i],f[j][k-1]*f[k][j+i]);
                    f[j][j+i]=max(f[j][j+i],g[j][k-1]*g[k][j+i]);// 负负得正

                    g[j][j+i]=min(g[j][j+i],g[j][k-1]*g[k][j+i]);
                    g[j][j+i]=min(g[j][j+i],f[j][k-1]*g[k][j+i]);
                        // 一个超大正数乘一个超大负数等于一个超大负数
                    g[j][j+i]=min(g[j][j+i],g[j][k-1]*f[k][j+i]);
                        // 一个超大正数乘一个超大负数等于一个超大负数
                }
            }
        }
    }
    for(int i=1;i<=n;i++){if(f[i][i+n-1]>ans){ans=f[i][i+n-1];
            p[cnt=1]=i;
        }
        else if(f[i][i+n-1]==ans)p[++cnt]=i;
    }
    cout<<ans<<endl;
    //printf("%lld\n",ans);
    for(int i=1;i<=cnt;i++)cout<<p[i]<<'';//printf("%lld ",p[i]);
    return 0;
}

  转载请注明: Sshwy's Blog [IOI1998]Polygon

 上一篇
矩阵乘法 矩阵乘法
矩阵定义在数学中,矩阵(Matrix)是一个按照长方阵列排列的复数或实数集合,最早来自于方程组的系数及常数所构成的方阵。例如,矩阵 A: A=\begin{bmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,m
2018.10.03
下一篇 
win10&ubuntu18 双系统 UEFI 安装 win10&ubuntu18 双系统 UEFI 安装
win10&ubuntu18 双系统 UEFI 安装前言安装成功之前倒腾半天,总算没什么损失,搞出来了特此发表 blog,也算是作一个好人吧 条件准备 电脑上已安装的 win10 系统 有网络的环境 (最好在下午 5 点前) ub
2018.10.01
  目录