POJ1179 Polygon [DP 매트릭스 체인 곱하기]

2752 단어
첫 번째 행렬 곱하기.
특별히 알고리즘 도론 안의 행렬 곱셈을 뒤적였는데 사실은 귀환으로 가장 좋은 해로 돌아갈 수 있다는 것을 느꼈다.
그러나 귀환 과정에 군더더기가 있다. 이런 군더기는 기억화 DP로 처리할 수 있는데 본질은 귀환 트리의 가지치기이다.
코드를 잘못 썼는데 AC 기분이 좋아서 몰라.
#include<iostream>
#include<vector>
#include<algorithm>
#define Abs(a) ((a)>0?(a):-(a))
#define Mod(a,b) (((a)-1+(b))%(b)+1)
using namespace std;
const int N=55;
const int inf=(1<<30);
int n;
struct Node
{
	char a;
	int w;
}node[N];
int mxw[N][N];
int mnw[N][N];//     ,             (  )    。
int solve(int start)
{
	memset(mxw,0,sizeof(mxw));
	memset(mnw,0,sizeof(mnw));
	for(int i=1;i<=n;i++)
	{
		mxw[i][i]=node[i].w;
		mnw[i][i]=node[i].w;
	}
	for(int i=2;i<=n;i++)
	{
		if(node[Mod(start+i,n)].a=='t')
		{
			mxw[Mod(i-1+start,n)][Mod(i+start,n)]=mxw[Mod(i-1+start,n)][Mod(i-1+start,n)]+mxw[Mod(i+start,n)][Mod(i+start,n)];
			mnw[Mod(i-1+start,n)][Mod(i+start,n)]=mxw[Mod(i-1+start,n)][Mod(i+start,n)];
		}
		else
		{
			mxw[Mod(i-1+start,n)][Mod(i+start,n)]=mxw[Mod(i-1+start,n)][Mod(i-1+start,n)]*mxw[Mod(i+start,n)][Mod(i+start,n)];
			mnw[Mod(i-1+start,n)][Mod(i+start,n)]=mxw[Mod(i-1+start,n)][Mod(i+start,n)];
		}
		for(int j=i-2;j>=1;j--)
		{
			int mx=-inf;
			int mn=inf;
			for(int k=j;k<=i-1;k++)
			{
				if(node[Mod(k+1+start,n)].a=='t')
				{
					mx=max(mxw[Mod(j+start,n)][Mod(k+start,n)]+mxw[Mod(k+1+start,n)][Mod(i+start,n)],mx);
					mn=min(mnw[Mod(j+start,n)][Mod(k+start,n)]+mnw[Mod(k+1+start,n)][Mod(i+start,n)],mn);
				}
				else
				{
					mx=max(mxw[Mod(j+start,n)][Mod(k+start,n)]*mxw[Mod(k+1+start,n)][Mod(i+start,n)],mx);
					mx=max(mnw[Mod(j+start,n)][Mod(k+start,n)]*mnw[Mod(k+1+start,n)][Mod(i+start,n)],mx);//          
					mn=min(mnw[Mod(j+start,n)][Mod(k+start,n)]*mnw[Mod(k+1+start,n)][Mod(i+start,n)],mn);
					mn=min(mnw[Mod(j+start,n)][Mod(k+start,n)]*mxw[Mod(k+1+start,n)][Mod(i+start,n)],mn);//                 。
					mn=min(mxw[Mod(j+start,n)][Mod(k+start,n)]*mnw[Mod(k+1+start,n)][Mod(i+start,n)],mn);
				}
			}
			mxw[Mod(j+start,n)][Mod(i+start,n)]=mx;
			mnw[Mod(j+start,n)][Mod(i+start,n)]=mn;
		}
	}
	return mxw[Mod(1+start,n)][Mod(n+start,n)];
}
int main()
{
	scanf("%d",&n);
	getchar();
	for(int i=1;i<=n;i++)
	{
		scanf(" %c%d",&node[i].a,&node[i].w);//%c       
		//printf("%c%d",node[i].a,node[i].w);
	}
	int ans=-inf;
	vector<int> vec;
	for(int i=0;i<n;i++)
	{
		int ret=solve(i);
		if(ret>ans)
		{
			vec.clear();
			vec.push_back(i+1);
			ans=ret;
		}
		else if(ret==ans)
		{
			vec.push_back(i+1);
		}
	}
	printf("%d
",ans); for(int i=0;i<vec.size()-1;i++) printf("%d ",vec[i]); printf("%d
",vec[vec.size()-1]); return 0; }

좋은 웹페이지 즐겨찾기