只A#3求助
查看原帖
只A#3求助
220824
yyz1005楼主2023/3/22 17:02
/*
dpa[i][j] 区间最大
dpi[i][j] 区间最小
spos 枚举断点
nva 新的数列
nop 新的操作列
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 60;
ll n;
ll val[N];
bool oper[N];
ll nva[N];
bool nop[N];
ll dpa[N][N],dpi[N][N];
ll res = -114514;
vector<ll> ap;
ll count(ll x,bool op,ll y){
	if(op) return x*y;
	return x+y;
}
int main(){
	cin >> n;
	for(ll i = 1; i <= n; i++){
		char operat;
		cin >> operat >> val[i];
		oper[i-1] = (operat=='x');
	}
	for(ll spos = 1; spos <= n; spos++){
		memset(dpa,0xcf,sizeof(dpa));
		memset(dpi,0x3f,sizeof(dpi));
		for(ll i = spos,j = 1; j <= n; i++,j++){
			if(i>n) i-=n;
			nva[j] = val[i];
			nop[j+1] = oper[i];
		}
		for(ll i = 1; i <= n; i++) dpa[i][i] = dpi[i][i] = nva[i];
		for(ll i = n; i >= 1; i--){
			for(ll j = i+1; j <= n; j++){
				for(ll k = i; k < j; k++){
					dpa[i][j] = max(dpa[i][j],max(max(count(dpa[i][k],nop[k+1],dpa[k+1][j]),count(dpa[i][k],nop[k+1],dpi[k+1][j])),max(count(dpi[i][k],nop[k+1],dpa[k+1][j]),count(dpi[i][k],nop[k+1],dpi[k+1][j]))));
					dpi[i][j] = min(dpi[i][j],min(min(count(dpa[i][k],nop[k+1],dpa[k+1][j]),count(dpa[i][k],nop[k+1],dpi[k+1][j])),min(count(dpi[i][k],nop[k+1],dpa[k+1][j]),count(dpi[i][k],nop[k+1],dpi[k+1][j]))));
				}
			}
		}
		if(dpa[1][n]>res){
			res = dpa[1][n];
			ap.clear();
			ap.push_back(spos);
		} else if(dpa[1][n]==res) ap.push_back(spos);
	}
	printf("%lld\n",res);
	for(auto v : ap) printf("%lld ",v);
	return 0;
}
2023/3/22 17:02
加载中...