![[//]: # (推荐题解模板,请替换blablabla等内容 ^^)
多边形游戏(可输出表达式)
代码
//#include <bits/stdc++.h>
#include<iostream>
#include<string>
#include<vector>
#include<string.h>
using namespace std;
#define int long long
const int N=110;
int a[N];
string b[N];
int dp[N][N][2];
vector<string> mark[N][N][2];
void function(int l ,int r,int k,int n1,int n2, int n3)
{
while(!mark[l][r][n1].empty())
{
mark[l][r][n1].pop_back();
}
mark[l][r][n1].push_back("(");
for(auto x:mark[l][k][n2])
{
mark[l][r][n1].push_back(x);
}
mark[l][r][n1].push_back(b[k]);
for(auto x:mark[k+1][r][n3])
{
mark[l][r][n1].push_back(x);
}
mark[l][r][n1].push_back(")");
}
void function_sum(int l ,int r,int k)
{
int x=dp[l][k][1] + dp[k+1][r][1];
int y=dp[l][k][0] + dp[k+1][r][0];
if(dp[l][r][1]<x)
{
dp[l][r][1]=x;
function(l,r,k,1,0,0);
}
if(dp[l][r][0]>y)
{
dp[l][r][0]=y;
function(l,r,k,0,0,0);
}
}
void function_mul(int l ,int r,int k)
{
int t=0;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
{
t=dp[l][k][i]*dp[k+1][r][j];
if(dp[l][r][1]<t)
{
dp[l][r][1]=t;
function(l,r,k,1,i,j);
}
}
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
{
t=dp[l][k][i]*dp[k+1][r][j];
if(dp[l][r][0]>t)
{
dp[l][r][0]=t;
function(l,r,k,0,i,j);
}
}
}
signed main()
{
int n;
int res = -0x3f3f3f3f;//求最大值,设置为无穷小
cin>>n;
for(int i = 1; i <=n; i++)
{
cin>>b[i]>>a[i];
b[i+n] = b[i];
a[i+n] = a[i];
}
for(int i=1;i<=2*n;i++)
for(int j=1;j<=2*n;j++)
{
if(i!=j)
{
dp[i][j][0]=0x3f3f3f;
dp[i][j][1]=-0x3f3f3f;
}
}
for(int i = 1; i <= 2*n; i++) {
dp[i][i][0] = a[i];
dp[i][i][1] = a[i];
string s=to_string(a[i]);
mark[i][i][0].push_back(s);
mark[i][i][1].push_back(s);
}
for(int len = 1; len < n; ++len)
for(int l = 1; l + len <= 2*n; ++l)
{
int r = l + len;
for(int k = l; k < r; ++k)
{
if(b[k+1] == "t")
{
function_sum(l,r,k);
}
else
{
function_mul(l,r,k);
}
}
}
int t=1;
for(int i = 1; i <= n; ++i) res = max(res,dp[i][i+n-1][1]);
cout<<res<<endl;
for(int i = 1; i <= n; ++i)
if(dp[i][i+n-1][1] == res) t=i,cout<<t<<" ";
//输出任意过程
// for(auto x:mark[t][t+n-1][1])
// cout<<x;
system("pause");
return 0;
}
----------](https://)