Bzoj 1783: [Usaco2010 Jan]Taking Turns"/>
Bzoj 1783: [Usaco2010 Jan]Taking Turns
原题网址:.php?id=1783
一排数,两个人轮流取数,保证取的位置递增,每个人要使自己取的数的和尽量大,求两个人都在最优策略下取的和各是多少。(1 <= N <= 700,000)
用f[i]记先手取第i位先手取最多能取多少,g[i]记先手取第i位后手取最多能取多少,从后往前推,对于一个i,后手最大能取的肯定是f[j] (j>i) 中最大的(不妨设这样的j为maxi),因为先手取了第i位后手在取第j(j>i)的时候就是先手了,他肯定会选一个最大的。而f[i]=a[i]+g[maxi],因为先手取了第i位后能取多少取决于后手下一步取哪一个,此时先手就变成了后手。
vara,f,g:array[0..700050] of int64;n,i,maxi:longint;
beginread(n);for i:=1 to n do read(a[i]);maxi:=n+1;for i:=n downto 1 dobeging[i]:=f[maxi];f[i]:=g[maxi]+a[i];if f[i]>=f[maxi]then maxi:=i;end;writeln(f[maxi],' ',g[maxi]);
end.
更多推荐
Bzoj 1783: [Usaco2010 Jan]Taking Turns
发布评论