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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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;
}