POJ1179 Polygon [DP 매트릭스 체인 곱하기]
특별히 알고리즘 도론 안의 행렬 곱셈을 뒤적였는데 사실은 귀환으로 가장 좋은 해로 돌아갈 수 있다는 것을 느꼈다.
그러나 귀환 과정에 군더더기가 있다. 이런 군더기는 기억화 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.