[TIOJ] 1029. A遊戲

題目連結:http://tioj.infor.org/problems/1029

---

本題第一眼看到可能會覺得是greedy，但其實這題不能greedy或者是我想不到好的準則XD，那不能greedy的話怎麼辦？就DP吧。不過說的簡單，實際上該如何DP呢？首先可以發現每次你要拿左邊或右邊都是希望拿了之後對方拿到的可以最小，所以不妨就讓子問題變成扣掉這格後對方可以拿到多少，基準點則是在只剩一個的時候，那必定只能拿到那格，有了這個之後就可以開始DP囉~因為所有區間總共只有$O(n^2)$個，所以總複雜度就$O(n^2)$

#include <stdio.h>
#include <bitset>
#include <unordered_map>

using std::bitset;
using std::unordered_map;

struct q{
	int first, second;
};

int arr[1000 + 10];
bitset<20000000 + 10> done;
unordered_map<int,q> saved;

q ask(int,int,bool);

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&arr[i]);
	q ans=ask(0,n,1);
	printf("%d %d",ans.first,ans.second);
	return 0;
}

q ask(int l, int r, bool fs){
	const int key = l*10000+r;
	if(done[key]) return saved[key];
	q rn={0};
	if(l+1==r) fs?rn.first=arr[l]:rn.second=arr[l];
	else{
		q ll=ask(l+1,r,!fs);
		q rr=ask(l,r-1,!fs);
		if(fs){
			if(ll.second < rr.second){
				rn=ll;
				rn.first += arr[l];
			}else{
				rn=rr;
				rn.first += arr[r-1];
			}
		}else{
			if(ll.first < rr.first){
				rn=ll;
				rn.second += arr[l];
			}else{
				rn=rr;
				rn.second += arr[r-1];
			}
		}
	}
	done[key]=1;
	saved[key]=rn;
	return rn;
}