洛谷P4342Polygen题解

传送
这是一道远古IOI题目
但是然鹅可是我还是调了好久
我们发现这很像石子合并，所以考虑用区间\(dp\)
首先考虑断边问题
这是个环，我们可以像石子合并那样，把链复制为原来的两倍来达到环的效果
如果我们是从\(i\)合并到\(j\),则相当于没有使用边\(i\),即断开边\(i\)
再来看\(dp\)式子
如果枚举的断点处的边是"+",则\(dp[i][j]=max\){\(dp[i][k]+dp[k+1][j]\)}
如果是\(\times\),那么可能会出现两个负数相乘然后得到更大的值的情况，所以我们还要考虑维护一个\(dp_{min}[i][j]\)
这样最大值可以由最大×最大，最小×最小，最大×最小（一正一负）更新而来
此时\(dp[i][j]=max\)\((dp[i][k]*dp[k+1][j],dp_{min}[i][k]*dp_{min}[k+1][j],dp[i][k]*dp_{min}[k+1][j],dp_{min}[i][k]*dp[k+1][j])\)
\(dp_{min}\)的维护：
加法：两个最小值相加即可
乘法：考虑最小×最小，最大×最小
\(Code\)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
int read()
{
	char ch=getchar();
	int x=0;bool f=0;
	while(ch<‘0‘||ch>‘9‘)
	{
		if(ch==‘-‘) f=1;
		ch=getchar();
	}
	while(ch>=‘0‘&&ch<=‘9‘)
	{
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return f?-x:x;
} 
int n,nd[109],ed[109];
ll dp[2][109][109],ans;
int main()
{
	n=read();
	for(int i=1;i<=2*n;i++)
	{
		if(i%2)
		{
			char ch=getchar();
			while(ch!=‘t‘&&ch!=‘x‘) ch=getchar();
			if(ch==‘t‘) ed[i/2+1]=1;
			if(ch==‘x‘) ed[i/2+1]=2;
		}
		else
			nd[i/2]=read();	
	}
	memset(dp[1],-0x3f,sizeof(dp[1]));
	memset(dp[0],0x3f,sizeof(dp[0]));
	ans=-2147483647;
	for(int i=1;i<=2*n;i++)
	{
		if(i>n) nd[i]=nd[i-n],ed[i]=ed[i-n];
		dp[0][i][i]=dp[1][i][i]=nd[i]; 
	} 
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i+len-1<=2*n;i++)
		{
			int j=i+len-1;
			for(int l=i;l<j;l++)
			{
				if(ed[l+1]==1)
				{
					dp[1][i][j]=max(dp[1][i][j],dp[1][i][l]+dp[1][l+1][j]);
					dp[0][i][j]=min(dp[0][i][j],dp[0][i][l]+dp[0][l+1][j]);
				}
				else
				{
					dp[1][i][j]=max(dp[1][i][j],dp[1][i][l]*dp[1][l+1][j]);
					dp[1][i][j]=max(dp[1][i][j],dp[0][i][l]*dp[0][l+1][j]);
					dp[1][i][j]=max(dp[1][i][j],dp[1][i][l]*dp[0][l+1][j]);
					dp[1][i][j]=max(dp[1][i][j],dp[0][i][l]*dp[1][l+1][j]);
					dp[0][i][j]=min(dp[0][i][j],dp[0][i][l]*dp[0][l+1][j]); 
				        dp[0][i][j]=min(dp[0][i][j],dp[1][i][l]*dp[0][l+1][j]);
				        dp[0][i][j]=min(dp[0][i][j],dp[0][i][l]*dp[1][l+1][j]);
				        dp[0][i][j]=min(dp[0][i][j],dp[1][i][l]*dp[1][l+1][j]);
				}
			}
		}
	} 
	for(int i=1;i+n-1<=2*n;i++)
	 ans=max(ans,dp[1][i][i+n-1]);
	printf("%lld\n",ans);
	for(int i=1;i<=n;i++)
	 if(dp[1][i][i+n-1]==ans) printf("%d ",i);
}

洛谷P4342Polygen题解

原文：https://www.cnblogs.com/lcez56jsy/p/12988674.html