【Luogu2975】轮流Taking Turns

来源和评测点

USACO10JAN
Luogu2975

题目

【题目大意】
两头奶牛Bessi和Dessie走过一条路吃草,共n(n<=700,000)个格子,
第i个格子有重量为Wi(1<=Wi<=2,000,000,000)的草,
两牛轮流走,一旦某头牛走过了一格,那么这格的草再也不可能被任一头奶牛吃,
每格的草只能被吃一次,所以两头牛只能往后走。

Bessi先走,每头牛每次都往最终自己能吃到最多草的格子走
(若有多个格子则选择第一个能吃到最多草的格子),
他们都知道对方也想吃到最多的草,问最后Bessi和Dessie各吃到的草的重量。
【输入格式】
第一行一个正整数n(n<=700,000)
接下来有n行,第i+1行是Wi(1<=Wi<=2,000,000,000)
【输出格式】
答案
【输入样例】
6
17
5
9
10
3
8
【输出样例】
27 17

分析

类似博弈,倒退DP
f[i]=从i到n最大收益
id[i]=达到f[i]用了的干草堆最后编号

对于干草堆i,存在两种选择:
1)用i,id[i]=i,f[i]=w[i]+f[id[i+1]+1] 即本堆干草+舍弃f[i+1]后最大收益
2)不用i,id[i]=id[i+1],f[i]=f[i+1]

代码

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll w[710000],f[710000],id[710000];
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
f[n]=w[n];id[n]=n;f[n+1]=0;
for(int i=n-1;i>=1;i--)
{
if(w[i]+f[id[i+1]+1]>=f[i+1])
{
f[i]=w[i]+f[id[i+1]+1];
id[i]=i;
}
else
{
f[i]=f[i+1];
id[i]=id[i+1];
}
}
printf("%lld %lld",f[1],f[id[1]+1]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2017-12/轮流Taking_Turns.html
转载请注明出处,谢谢!

给我投食吧,您的支持将鼓励我继续创作!