luoguP2975 [USACO10JAN]轮流Taking Turns

题目

---

$f[i]$表示$i..n$能取到的最大和

$g[i]$表示$i..n$取到最大和时，最先取到的点

从后往前跑，对于一个点，考虑它取不取

​ 如果不取，$f[i]=f[i+1],g[i]=g[i+1]$

​ 如果取，$f[i]=f[g[i+1]+1]+a[i],g[i]=i$

因为$g[i+1]$表示$i+1$取最大和时，最先取到的点，如果取i，那么下一头牛就会取$i+1..n$的最大和，也就是取第$g[i+1]$个。那么当前这头牛就只能从$g[i+1]+1$开始取，所以是$f[i]=f[g[i+1]+1]+a[i]$

---

code

#include<bits/stdc++.h>
#define ll long long
#define N 700010
#define mem(a,b) memset(a,b,sizeof(a))
#define fsb(a,b,c) for(ll a=b;a<=(c);a++)
#define fbs(a,b,c) for(ll a=b;a>=(c);a--)
using namespace std;
ll n,f[N],g[N],a[N];
template<typename qw>inline void rll(qw &x){
 x=0;qw f=1;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
int main(){
 rll(n);fsb(i,1,n)rll(a[i]);mem(f,0);mem(g,0);
 fbs(i,n,1){
  if((g[i+1]==0)||(f[g[i+1]+1]==0)){
   f[i]=a[i];g[i]=i;
  }else{
   f[i]=a[i]+f[g[i+1]+1];g[i]=i;
  }
  if(f[i+1]>f[i])f[i]=f[i+1],g[i]=g[i+1];
 }
 printf("%lld %lld\n",f[1],f[g[1]+1]);
 return 0;
}