区间DP最后一个WA了求调
查看原帖
区间DP最后一个WA了求调
107527
chenkaiwen楼主2021/12/9 17:55
#include<bits/stdc++.h>
using namespace std;
struct as{
	int v,type;
};
vector<as>G[100];
int f[100][100];
int a[100],l[100];
int n;
#define mmd(x) (int)(x%n?x%n:n)
#define md(x) mmd((int)(x))
#define mem(x) for(int I=1;I<=n;I++){for(int J=1;J<=n;J++)x[I][J]=-32770;l[I]=0;}
void In(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		char t1;int t2,type;
		cin>>t1>>t2;
		type=t1=='t'?1:2;
		G[i].push_back((as){
			md(i+1),type
		}) ;
//		cout<<i<<"-"<<md(i+1)<<endl; 
		a[i]=t2;
	}
}
void dfs(int end,int u,int de){
//	cout<<u<<endl;
	f[de][de]=a[u];
	l[de]=G[u][0].type;
	if(u!=end)dfs(end,G[u][0].v,de+1);
}
vector<int>ans;
void cls(){
	while(ans.size())ans.pop_back();
}
void Work(){
	int haq=-32770;
	for(int q=1;q<=n;q++){
		mem(f);
		dfs(q,md(q+1),1);
//		cout<<md(q+1)<<' '<<int(q)<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j+i<=n;j++){
				for(int k=j;k<j+i;k++){
//					cout<<j<<" "<<j+i<<" "<<f[j][j+i]<<" ";
					f[j][j+i]=max(f[j][j+i],l[md(k+1)]==1?f[j][k]+f[k+1][j+i]:f[j][k]*f[k+1][j+i]);
//					cout<<f[j][j+i]<<" "<<j<<' '<<k<<" "<<k+1<<" "<<j+i<<' '<<f[j][k]<<" "<<f[k+1][j+i]<<endl;
				}
			}
		}
		if(haq<f[1][n]){
			haq=f[1][n];
			cls();
		}
		if(haq==f[1][n])ans.push_back(md(q+1));
	}
	printf("%d\n",haq);
	sort(ans.begin(),ans.end());
	for(int i=0;i<ans.size();i++)printf("%d ",ans[i]);
}
int main(){
	In();
	Work();
    return 0;
}

2021/12/9 17:55
加载中...