SRM 269 DIV1 Hard PieSharing

問題 Editorial

問題

Nつに分割されたパイがある。Nは3の倍数である。そのそれぞれの部分の面積piecesが与えられる。
これを自分と相手で交互に食べ、自分が食べる面積を最大化したい。
自分は、任意の部分を1つ選び、それを食べることができる。
次に、相手は直前に自分が食べた部分の両隣のパイを2つとも食べなければいけない。
これを繰り返す。
食べられる最大の面積を求めよ

• 3 <= N <= 48
• 1 <= pieces[i] <= 100
• sum pieces = 100

解答

Editorialを参考にした。
自分の食べるパイ(N/3)つを最初に選択するという考え方をする。
まず、明らかに、どれか2つが隣接しているような選び方では食べられない。それを食べようとするとその隣を食べられてしまうので。
逆に、どれも隣接していないような(N/3)つの選び方ならば必ず食べることが出来る。
直感的には、選択パイの数は少ないので常に隙間が多く、隙間を維持したところを食べられる感じ。
さてこの組み合わせを選ぶのは普通に円DPすればいい

コード

#include <vector>
#include <cstring>
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef vector<int> vi;  
int dp[2][55][20];
struct PieSharing {
	vi p; int n;
	int rec(bool leftmost, int i, int count) {
		if(dp[leftmost][i][count] != -1) return dp[leftmost][i][count];
		int r = -INF;
		if(i == n) {
			if(count == 0) r = 0;
			else ;
		} else if(i == n-1) {
			if(leftmost) r = max(r, rec(leftmost, i+1, count));
			else {
				r = max(r, rec(leftmost, i+1, count));
				if(count) r = max(r, p[i]+rec(leftmost, i+1, count-1));
			}
		}else {
			r = max(r, rec(leftmost, i+1, count));
			if(count) r = max(r, p[i]+rec(leftmost, i+2, count-1));
		}
		return dp[leftmost][i][count] = r;
	}
	int share(vector <int> pieces) {
		p = pieces; n = p.size();
		mset(dp, -1);
		return max(p[0]+rec(true, 2, n/3-1), rec(false, 1, n/3));
	}
};