社区讨论

蒟蒻求助,WA了两个点的说嘤嘤嘤

P4342[IOI 1998] Polygon参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi6wmt0b
此快照首次捕获于
2025/11/20 12:01
4 个月前
此快照最后确认于
2025/11/20 12:01
4 个月前
查看原帖
CPP
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int f[105][105][2],op[105];
char s;

int main(){
	//freopen("1.in","r",stdin);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>s;
		if(s=='t')op[i-1]=1;
		scanf("%d",&f[i][i][1]);
		f[i+n][i+n][1]=f[i+n][i+n][0]=f[i][i][0]=f[i][i][1];
		op[i+n-1]=op[i-1];
	}
	
	for(int len=2;len<=n;len++){
		for(int i=1;i<=n*2-len+1;i++){
			int j=i+len-1;
			for(int k=i;k<j;k++){
				if(op[k]){
					f[i][j][1]=max(f[i][j][1],f[i][k][1]+f[k+1][j][1]);
					f[i][j][0]=min(f[i][j][0],f[i][k][0]+f[k+1][j][0]);
				}
				else{
					f[i][j][1]=max(max(f[i][j][1],f[i][k][1]*f[k+1][j][1]),f[i][k][0]*f[k+1][j][0]);
					f[i][j][0]=min(min(f[i][j][0],f[i][k][0]*f[k+1][j][0]),min(f[i][k][0]*f[k+1][j][1],f[i][k][1]*f[k+1][j][0]));
				}
			}
		}
	}
	int mx=0;
	for(int i=1;i<=n;i++){
		mx=max(mx,f[i][i+n-1][1]);
	}
	printf("%d\n",mx);
	for(int i=1;i<=n;i++){
		if(mx==f[i][i+n-1][1])printf("%d ",i);
	}
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...