环状

#include <bits/stdc++.h>
using namespace std;
#define li long long 
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
li vertices[101];
bool edge[101];
li f[101][101];
li m[101][101]; 
const li limin=-9223372036854775807;
const li limax=9223372036854775807;
li tmax=limin;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		char m;
		cin>>m;
		edge[i]= m=='x'?1:0;//1是乘，0是+ 
		cin>>vertices[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=limin;
			m[i][j]=limax;
		}
	}
	for(int i=1;i<=n;i++){
		f[i][i]=vertices[i];
		m[i][i]=vertices[i];
	}
	for(int len=2;len<=n;len++){
		for(int i=1;i<=n;i++){
			int r=(i+len-2)%n+1;
			for(int k=i;k<=i+len-2;k++){
				if(edge[k%n+1]){
					li p=max(max(f[i][(k-1)%n+1]*f[k%n+1][r],m[i][(k-1)%n+1]*m[k%n+1][r]),max(f[i][(k-1)%n+1]*m[k%n+1][r],f[i][(k-1)%n+1]*m[k%n+1][r]));
					f[i][r]=max(f[i][r],p);
					li q=min(min(m[i][(k-1)%n+1]*m[k%n+1][r],f[i][(k-1)%n+1]*f[k%n+1][r]),min(f[i][(k-1)%n+1]*m[k%n+1][r],f[i][(k-1)%n+1]*m[k%n+1][r]));
					m[i][r]=min(m[i][r],q);

				}else{
					f[i][r]=max(f[i][r],f[i][(k-1)%n+1]+f[k%n+1][r]);
					m[i][r]=min(m[i][r],m[i][(k-1)%n+1]+m[k%n+1][r]);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(f[i][(i-2)%n+1]>tmax){
			tmax=f[i][(i-2)%n+1];
		}
	}
	cout<<tmax<<endl;
	for(int i=1;i<=n;i++){
		if(f[i][(i-2)%n+1]==tmax){
			cout<<i<<' ';
		}
	}
	
	return 0;
}

断链的区间dp

#include <bits/stdc++.h>
using namespace std;
#define li long long 
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
li vertices[101];
bool edge[101];
li f[101][101];
li m[101][101]; 
const li limin=-9223372036854775807;
const li limax=9223372036854775807;
li tmax=limin;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		char m;
		cin>>m;
		edge[i]= m=='x'?1:0;//1是乘，0是+ 
		cin>>vertices[i];
	}
	for(int i=1;i<=n;i++){
		vertices[i+n]=vertices[i];
		edge[i+n]=edge[i];
	} 
	for(int i=1;i<=2*n;i++){
		for(int j=1;j<=2*n;j++){
			f[i][j]=limin;
			m[i][j]=limax;
		}
	}
	for(int i=1;i<=n;i++){
		f[i][i]=vertices[i];
		m[i][i]=vertices[i];
	}
	for(int len=2;len<=n;len++){
		for(int i=1;i<=2*n-1&&i+len-1<=2*n;i++){
			int r=i+len-1;
			for(int k=i;k<=i+len-2;k++){
				if(edge[k+1]){
					li p=max(max(f[i][k]*f[k+1][r],m[i][k]*m[k+1][r]),max(f[i][k]*m[k+1][r],f[i][k]*m[k+1][r]));
					f[i][r]=max(f[i][r],p);
					li q=min(min(m[i][k]*m[k+1][r],f[i][k]*f[k+1][r]),min(f[i][k]*m[k+1][r],f[i][k]*m[k+1][r]));
					m[i][r]=min(m[i][r],q);
				}else{
					f[i][r]=max(f[i][r],f[i][k]+f[k+1][r]);
					m[i][r]=min(m[i][r],m[i][k]+m[k+1][r]);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(f[i][i+n-1]>tmax){
			tmax=f[i][i+n-1];
		}
	}
	cout<<tmax<<endl;
	for(int i=1;i<=n;i++){
		if(f[i][i-1]==tmax){
			cout<<i<<' ';
		}
	}
	
	return 0;
}