UVa-10891 : Game of Sum

問題概要

長さN(<100)の配列があり、先手と後手が交互に右端か左端を選んで連続する1個以上の部分列をとる。和を最大にしたい。お互い最善を尽くしたとき先手は後手よりどれだけ大きいスコアになるかを求める問題。

解法

連続する区間を残すので[from, to)型のDP。
入力がファイル読み込みって書いてあったけど実際は標準入力からの読み込みだった。

acceptされたコード

計算量O(N^3)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 100;

int N;
int as[MAX_N];
int accum[MAX_N + 1];
int memo[MAX_N + 1][MAX_N + 1];
bool visited[MAX_N + 1][MAX_N + 1];

bool init(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d", as + i);
	}
	for(int i=0; i<N; i++){
		accum[i + 1] = accum[i] + as[i];
	}
	memset(visited, false, sizeof(visited));

	return N > 0;
}

int rec(int from, int to){
	if(visited[from][to]){
		return memo[from][to];
	}
	visited[from][to] = true;

	int& ret = memo[from][to] = accum[to] - accum[from];

	if(to - from == 1){
		return ret = as[from];
	}

	//前からとる
	for(int i=from+1; i<to; i++){
		ret = max(ret, accum[i] - accum[from] - rec(i, to));
	}
	//後からとる
	for(int i=from+1; i<to; i++){
		ret = max(ret, accum[to] - accum[i] - rec(from, i));
	}

	return ret;
}

int solve(){
	return rec(0, N);
}

int main(){
	//freopen("e.in", "r", stdin);
	while(init()){
		printf("%d\n", solve());
	}

	return 0;
}