sum 게임 Game of sum uva 10891 동적 기획 메모(기억화 검색)

1283 단어 동적 기획
제목의 대의는 하나의 정수로 구성된 서열이 있는데 두 사람이 번갈아 숫자를 뽑으면 한쪽에서 하나 또는 여러 개만 뽑을 수 있다(여기 대백서에 잘못 썼다). 모든 숫자가 다 뽑혔을 때 뽑은 모든 숫자의 합을 이 유저의 점수로 하고 A의 점수-B의 점수를 구한다. 두 사람은 모두 가장 좋은 방안으로 값을 얻는다.이 문제는 동적 기획을 사용하여 해답을 구한다. 하위 문제는 i~j의 하위 서열이 먼저 얻은 점수의 최대 값이다.
d[i][j]를 설정하면 서열i~j의 선취수를 나타내는 최대 점수는 d[i][j]=sum[i][j]-min(d[i+1][j], d[i+2][j], d[i+3][j],..., d[j][j],..., d[j][j][j], [j-1], d[i][j-2], d[i][j-3], d[i][i], 0이다.0은 모든 수를 먼저 뽑았다는 것을 의미한다.따라서 마지막 계산 결과는 d[1][n]-(sum[1][n]-d[i][n]) 즉 2*d[1][n]-sum[1][n]이다.동적 기획 사용 비망록 방법.
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 200
#define INF 1000000000
int s[MAXN];
int n;
int d[MAXN][MAXN];
int sum[MAXN];
int dp(int i,int j)
{
	if(d[i][j]!=INF)return d[i][j];
	if(i==j)return sum[i]-sum[i-1];
	int t=0;
        for(int ii=i+1;ii<=j;ii++)
		t=min(t,dp(ii,j));
	for(int jj=j-1;jj>=i;jj--)
		t=min(t,dp(i,jj));
	d[i][j]=sum[j]-sum[i-1]-t;
	return d[i][j];
}
int main()
{
	while(scanf("%d",&n),n)
	{
		sum[0]=0;
		for(int i=0;i<MAXN;i++)
			for(int j=0;j<MAXN;j++)d[i][j]=INF;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&s[i]);
			sum[i]=sum[i-1]+s[i];
		}
                cout<<dp(1,n)*2-sum[n]<<endl;
        }

}

 

좋은 웹페이지 즐겨찾기