[Elite 2010 January Competition Gold 【hayturn】]博弈类动态规划★★

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1783
【吐槽】
唉唉唉唉。。。
看了解题报告才会。太水了= =。。。
一开始看错题，写了个dp，样例都不过，后来看了解题报告才理解了题意。。。
囧
【算法分析】
下面基本是对解题报告的翻译：
令Fa[i]表示当前到这只牛选，选的范围是[i,n]，然后这只牛到最后最多能得到多少分？
令Fb[i]表示当前到另外一只牛选，选的范围是[i,n]，然后到最后这只牛最多能得到多少分？
然后我们应当注意到，主动权在选的那只牛手里。
现在我们有两种决策。
1、选第i格这个权。
那么Fa[i]=Fb[i+1]+w[i];
同时Fb[i]=Fa[i+1];
2、不选第i格这个权。
那么Fa[i]=Fa[i+1];
同时Fb[i]=Fb[i+1];

注意到主动权在当前选那只牛的手里，那么我们以当前选这只牛为上帝进行决策。
就是要取最大的Fa[i]。
所以只要比较Fb[i+1]+w[i]和Fa[i+1]就可以了。。。
【其它】cin取消同步以后原来不是很慢！！！就是800+MS。我用scanf也就500+MS…
当然，要G++才可以。就像外挂一样。
【CODE】
#include using namespace std;
typedef long long lld;
const lld N=705555;
lld n,w[N],Fa[N],Fb[N];

void solve(){
Fa[n]=w[n];
Fb[n]=0;
int i;
for (i=n-1;i>=1;i–)
if (Fb[i+1]+w[i]>=Fa[i+1]){
Fa[i]=Fb[i+1]+w[i];
Fb[i]=Fa[i+1];
}
else{
Fa[i]=Fa[i+1];
Fb[i]=Fb[i+1];
}
cout << Fa[1] << " " << Fb[1] << endl;
}

int main(){
ios::sync_with_stdio(false);
cin >> n;
for (lld i=1;i<=n;i++) cin >> w[i];
solve();
return 0;
}