题意描述

多边形是一个玩家在一个有 $n$个顶点的多边形上的游戏，

如图所示，其中$n＝4$。每个顶点有点权，每个边有一个运算符，是 $+$ 或 $\times$ 的其中一种。

这个游戏的过程如下：

  1. 删除其中任意一条边。
  2. 选择一条边连接的两个顶点，并用边上的运算符计算两个点权得到的结果来替换这两个顶点的点权
  3. 重复过程 $2$ ，直到只有一个点为止。

举个例子，对于上面的图，我们可以先移除编号为 $3$ 的边。之后选择计算编号为 $1$ 的边，然后计算编号为 $4$ 的边，最后，计算编号为 $2$ 的边。

最后得到的结果为 $0$。

现在问题来了，给定一个多边形，请计算最高可以得到的分数。

输入格式

第一行给出数字 $n$，为多边形的总边数。

第二行描述这个多边形，一共有 $2 \times n$ 个读入，每两个读入中第一个是字符，第二个是数字。

第一个字符为第一条边的计算符号( $t$ 代表 $+$，$x$ 代表 $\times$)，第二个代表顶点上的数字。

输出格式

输出共有两行，第一行，输出最高的分数。

在第二行，输出所有可能的被清除后的边仍能得到最高得分的列表。请按照递增的顺序给出。

Input & Output ‘s examples

Input ‘s eg

4
t -7 t 4 x 2 x 5

Output ‘s eg

33
1 2

数据范围与约定

对于 $100\%$ 的数据，满足 $1 \leq n \leq 50$，所有输入数据均在$\lbrack -2^{16} , 2^{16} \rbrack$ 范围内。

分析

上古时期的 $\text{IOI}$ 签到题……

题目中要求求出所有可能情况中的最大值，无疑是区间$\text{dp}$。

又因为题目中给出的是一个环，考虑断环成链，即$a_{i + n} = a_i$。

之后考虑如何 $\text{dp}$，设 $f[i][j]$ 表示从 $i$ 到 $j$ 的最大得分。初始时，有 $f[i][i] = a[i]$

对于加法操作，则有：

但乘法操作会出现负负得正的情况，因此我们还需要记录最小值。设 $g[i][j]$ 表示从 $i$ 到 $j$ 的最小得分，则有：

对于乘法操作，则有：

最后统计 ，并记录答案输出即可。

时间复杂度为 $O(n^3)$ ，足以跑过全部数据。

剩下的细节见代码注释。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;

ll f[105][105] , g[105][105]; //f[i][j] i -> j的最大得分 , g[i][j] i -> j的最小得分

/*
    f[i][j] = max(f[i][j] , f[i][k] + f[k+1][j]);
    g[i][j] = min(g[i][j] , g[i][k] + g[k+1][j]);
*/ 

int a[M]; 
char c[M];

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    int n; cin >> n;
    rep(i , 1 , n){
        cin >> c[i] >> a[i];    //用 cin 避免读入空格
        c[i + n] = c[i] , a[i + n] = a[i];  //断环成链
    }
    clean(f , -0x3f3f3f3f) , clean(g , 0x3f3f3f3f);
    rep(i , 1 , 2 * n) f[i][i] = g[i][i] = a[i];    //初始化dp状态
    rep(l , 1 , n){
        for(int i = 1; i + l <= 2 * n; i ++){
            int j = i + l;
            for(int k = i; k < j; k ++){
                if(c[k + 1] == 't'){    //加法操作
                    f[i][j] = max(f[i][j] , f[i][k] + f[k + 1][j]);
                    g[i][j] = min(g[i][j] , g[i][k] + g[k + 1][j]);
                }
                else if(c[k + 1] == 'x'){   //乘法操作
                    f[i][j] = max(f[i][j] , max(f[i][k] * f[k + 1][j] , max(f[i][k] * g[k + 1][j] , max(g[i][k] * f[k + 1][j] , g[i][k] * g[k + 1][j]))));
                    g[i][j] = min(g[i][j] , min(g[i][k] * g[k + 1][j] , min(g[i][k] * f[k + 1][j] , min(f[i][k] * f[k + 1][j] , f[i][k] * g[k + 1][j]))));
                }
            }
        }
    }
    ll res = -INT_MAX;  //统计最后答案
    rep(i , 1 , n) res = max(res , f[i][i + n - 1]); 
    printf("%lld\n" , res);
    rep(i , 1 , n){
        if(f[i][i + n - 1] == res) printf("%d " , i);
    }

    return 0;
}

THE END