Turns"/>
bzoj1783 [Usaco2010 Jan]Taking Turns
一开始以为是博弈论(虽然确实是博弈。。)但是后来发现要用dp。。
顺着dp炸了。。
只好倒过来dp。。(按照性质就应该从后往前好吗。。)
从第i个位置开始,第一个为f[1][i],第二个为f[2][i]。
然后我们倒推,,f[1][i]肯定是取当前的a[i]或者i+1-n中最大的那个,取一个max,然后f[2][i]取另外一个就好啦。。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,m;
ll f[3][N],a[N];
int main()
{scanf("%d",&n);fo(i,1,n)scanf("%d",&a[i]);int pos=n;ll mx=0;fd(i,n,1){f[1][i]=mx;f[2][i]=f[2][pos];if (f[1][i]<=f[2][pos]+a[i]){f[1][i]=f[2][pos]+a[i];mx=f[1][i];pos=i;f[2][i]=f[1][i+1];}}printf("%lld %lld\n",f[1][1],f[2][1]);return 0;
}
更多推荐
bzoj1783 [Usaco2010 Jan]Taking Turns
发布评论