SRM366 div2 hard
最初に選ぶ所を決めたら、1回選ぶごとに右と左に分けて考えられる
ターン制の問題は実装が多くなるから嫌い
たぶんDPでもできる。
ていうかこのコードはちょっと頭が悪いので計算量が2倍になっている
#include <cstring> #include <cstdio> #include <utility> #include <vector> using namespace std; class PickGuitars { public: vector<int> guiter; pair<int,int> cache[50][50][2]; pair<int,int> rec(int f,int e,bool isPlayer) { pair<int,int> &r=cache[f][e][(isPlayer)?1:0]; if(r.first!=-1) ; else if(f==e) r.first=0,r.second=0; else { if(isPlayer) { r.first=-1; for(int i=f;i<e;i++) { pair<int,int> p,q; p=rec(f,i,false),q=rec(i+1,e,false); if(r.first<p.first+guiter[i]+q.first) { r.first=p.first+guiter[i]+q.first; r.second=p.second+q.second; } } } else { r.second=-1; for(int i=f;i<e;i++) { pair<int,int> p,q; p=rec(f,i,true),q=rec(i+1,e,true); if(r.second<p.second+guiter[i]+q.second) { r.second=p.second+guiter[i]+q.second; r.first=p.first+q.first; } } } } return r; } int maxValue(vector<int> guitarValues) { int n=guitarValues.size(); int ans=0; for(int i=0;i<n;i++) { vector<int> v; for(int j=i+1;j<n;j++) v.push_back(guitarValues[j]); for(int j=0;j<i;j++) v.push_back(guitarValues[j]); guiter=v; memset(cache,-1,sizeof(cache)); ans=max(ans,guitarValues[i]+rec(0,n-1,false).first); } return ans; } };