UVA 10891 - Game of Sum(게임+구간 DP+기억력 검색)

Root
  

10891 - Game of Sum

Time limit: 3.000 seconds
This is a two player game. Initially there are n integer numbers in an array and players A and B get chance to take them alternatively. Each player can take one or more numbers from the left or right end of the array but cannot take from both ends at a time. He can take as many consecutive numbers as he wants during his time. The game ends when all numbers are taken from the array by the players. The point of each player is calculated by the summation of the numbers, which he has taken. Each player tries to achieve more points from other. If both players play optimally and player A starts the game then how much more point can player A get than player B?
Input The input consists of a number of cases. Each case starts with a line specifying the integer n (0 < n ≤ 100), the number of elements in the array. After that, n numbers are given for the game. Input is terminated by a line where n = 0.
Output For each test case, print a number, which represents the maximum difference that the first player obtained after playing this game optimally.
Sample Input 4 4 -10 -20 7 4 1 2 3 4 0
Sample Output 7 10
제목은 n더미의 돌이 있다는 뜻으로 해석할 수 있다. A와 B 두 사람이 한 번에 그 중에서 돌을 들고 한 사람이 최대 연속으로 k더미를 들 수 있다. 즉, 제한을 두지 않고 A가 먼저 든다.둘 다 가장 좋은 상황에서 A는 B보다 몇 개 더 받을 수 있느냐고 물었다.
우선 이것은 바둑 문제에 속한다. 채소닭은 바둑에 대한 이해가 매우 적고 구간DP는 그래도 된다.구간 i, j를 매거한 다음에 끊임없이 값을 얻는 조작이다.먼저 원수 그룹을 처리해야 한다. 두 층의 for가 순환하고 외층의 i는 0에서 n-1, 내층의 j는 i에서 마지막까지sum수 그룹은 i에서 j까지의 합을 저장한다.그리고 dfs를 진행합니다.나머지는 구간 dp+기억화 검색입니다. 구체적으로 실현하려면 코드를 보십시오. 한눈에 알 수 있습니다.
코드 구현:

#include
#include
#include
#include
#include
#include
#define ll long long
#define mset(a,x) memset(a,x,sizeof(a))

using namespace std;
const double PI=acos(-1);
const int inf=0x3f3f3f3f;
const double esp=1e-6;
const int maxn=250005;
const int mod=1e9+7;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll inv(ll b){if(b==1)return 1; return (mod-mod/b)*inv(mod%b)%mod;}
ll fpow(ll n,ll k){ll r=1;for(;k;k>>=1){if(k&1)r=r*n%mod;n=n*n%mod;}return r;}
int dp[105][105],map[105],visit[105][105],sum[105][105],n;

int dfs(int l,int r)
{
	
	if(l>r)
	return 0;
	if(visit[l][r])                                //    ，  DP[l][r] 
	return dp[l][r];
	int ans=-1e9;
	visit[l][r]=1;                                 //   
	
	for(int k=1;k<=r-l+1;k++)
	{
		ans=max(ans,sum[l][r]-min(dfs(l+k,r),dfs(l,r-k)));   //ans             ， sum[l][r]               
	}
	dp[l][r]=ans;                                           //    
	return ans;
}

int main()
{
	int i,j,k;
	while(cin>>n&&n)
	{
		mset(dp,0);
		mset(visit,0);
		for(i=0;i>map[i];
		
		for(i=0;i