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;
}

code

Social