题解 - Vijos

4

PowderHan LV 10 @ 2017-05-08 12:42:56

/*
问题描述:
给出一个有n个数序列Q1,Q2,Q3...Qn,做一个博弈问题.
两人轮流重序列的两端取走一个数,在第二个人以最佳策略取数的情况下求第一个人取数的和的最大值.
我们来看    因为对手每次都会选择最优的来做
所以这道题就可以转换为最优性问题来做OTZ
那么就是DP了
我们设f[i,j]表示第i个数到第j个数在这个区间内先拿数的人最大能拿到的和
我写的程序是直接递推的区间长度即j-i
我们可以知道
在区间[i,j]中要得到最优的结果
而我们只有从头和尾取数的两种方法
也就是每个状态只有两种决策
而这又构成最优子结构性质了(这个很好推导吧)
则有状态转移方程
f[i,j]=sum[i,j]-min(f[i+1,j],f[i,j-1]);
初值为f[i][i]=a[i]
怎么解释这个状态转移方程呢？
我们这么看   这是一道博弈题
即我们在[i,j]这个区间如果取了i这个点对应的数
那么下一个人取数的时候问题就变成了怎么在[i+1,j]取到最大的数
如果取了j对应的同理就变成了f[i,j-1]
而只有两个人  如果对方取得数越多
自己取到的数肯定越少
而sum[i][j]是不变的  所以我们要尽可能让对方在你取完了某个数之后
他能得到的最大的值最小 而这个sum[i][j]减去他取得的最小的值
肯定就是你取得的最大的值
那么理清了这个关系答案就很简单了
我们最后的答案得出了f[1][n]表示整个能取到的最大值
那么如果小杉先手
答案就是f[1][n]
不然f[1][n]肯定就被对手选走了
他就会更少了就是sum[1][n]-f[1][n]
有点迭代交换的感觉   非常经典的博弈题
好题QWQ
果然窝还是太弱惹    想了半天才弄通
这里还想再提到的就是关于这个递推顺序的故事了
我们知道  lrj大神说过
状态和状态转移方程决定了天然的递推顺序
所以说我们要好好考虑状态很递推顺序的关系
我们可以看到状态转移中
当前的状态是从两个比当前状态对应的区间长度少1的状态转移而来
所以我们很容易想到
从区间长度短到长递推转移即可
Orz果然还是要深思 
*/
#include <iostream>
#include <cstdio>
using namespace std;

int f[2002][2002];
int a[2002];
int total[2002];

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        total[i]=total[i-1]+a[i];
        f[i][i]=a[i];
    }
    for(int i=1;i<=n;i++)//枚举区间长度
    {
        for(int j=1;j+i<=n;j++)
            f[j][j+i]=(total[j+i]-total[j-1])-min(f[j+1][j+i],f[j][j+i-1]);
    }
    if(k==1)
        printf("%d",f[1][n]);
    else
        printf("%d",total[n]-f[1][n]);
}

0

SHZhang LV 8 @ 2018-09-15 16:58:37

/*
f[i][j][0]代表在i到j这个区间wind先取的话，小杉最大能获得的分数
f[i][j][1]代表在i到j这个区间小杉先取的话，小杉最大能获得的分数
注意一定要按照小的区间到大的区间这个顺序
*/
#include <cstdio>
#include <algorithm>
using namespace std;

int n;
int order;

int a[2001];

int f[2001][2001][2];

int main()
{
    scanf("%d%d", &n, &order);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    for (int s = 1; s <= n; s++) {
        for (int i = 0; i < n - s + 1; i++) {
            f[i][i + s - 1][0] = min(f[i+1][i+s-1][1], f[i][i+s-2][1]);
            f[i][i + s - 1][1] = max(f[i+1][i+s-1][0] + a[i], f[i][i+s-2][0] + a[i+s-1]);
        }
    }
    printf("%d", f[0][n-1][order]);
    return 0;
}

0

逗比syz LV 8 @ 2016-11-11 21:10:46

测试数据 #0: Accepted, time = 31 ms, mem = 16260 KiB, score = 20
测试数据 #1: Accepted, time = 31 ms, mem = 16260 KiB, score = 20
测试数据 #2: Accepted, time = 31 ms, mem = 16256 KiB, score = 20
测试数据 #3: Accepted, time = 31 ms, mem = 16256 KiB, score = 20
测试数据 #4: Accepted, time = 31 ms, mem = 16252 KiB, score = 20
Accepted, time = 155 ms, mem = 16260 KiB, score = 100

今天光棍节，刷道题来纪念一下我过的第15个光棍节

自己的方程蠢得一塌糊涂
f[i,j]:=max{max{f[i+2,j]+ai，f[i+1,j-1]+ai}，max{f[i+1,j-1]+aj，f[i,j-2]+aj}}
然后找边界找到疯，索性放弃了，于是新的方程就和楼下大牛们的一样了。。。

0

Aurora__lucky LV 9 @ 2015-08-03 10:20:28

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int N,first,Q[2005],S[2005],dp[2005][2005];
void is()
{
memset(dp,-1,sizeof(dp));
scanf("%d %d",&N,&first);
for(int i=1;i<=N;i++) scanf("%d",&Q[i]);
S[0]=0;
S[1]=Q[1];
for(int i=2;i<=N;i++)
S[i]=S[i-1]+Q[i];
}
int SUM(int l,int r)
{
return S[r]-S[l-1];
}
int solve(int l,int r)
{
if(dp[l][r]!=-1)
return dp[l][r];
if(l==r)
return Q[l];
int M;
M=SUM(l+1,r)-solve(l+1,r)+Q[l];
M=max(M,SUM(l,r-1)-solve(l,r-1)+Q[r]);
return dp[l][r]=M;
}
int main()
{
is();
if(first) printf("%d\n",solve(1,N));
else printf("%d\n",SUM(1,N)-solve(1,N));
return 0;
}

0

奇异夸克 LV 7 @ 2009-11-07 16:13:19

显然是DP，但是怎么都不过，最后气得我写了个记忆化搜索，一下就AC了

0

laz LV 10 @ 2009-11-01 20:15:57

编译通过...

├ 测试数据 01：答案正确... 9ms

├ 测试数据 02：答案正确... 40ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 56ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：114ms

。。

Flag 　　Accepted

题号　　P1202

类型(?) 　　博弈论

通过　　600人

提交　　2048次

通过率　　29%

难度　　2

第600人。

悲剧。

for i:=1 to n-i do

....

0

尖端才子 LV 10 @ 2009-10-25 11:45:59

Accepted 有效得分：100 有效耗时：579ms

1次AC……

BS sunny……

方法：纯DP

转移方程:

设f表示先拿时在i到j这一段的最大得分

f:=max(a[i]+(sum[j]-sum[i]-f),a[j]+(sum[j-1]-sum-f));

初始化：f:=a[i];

如果先拿则输出f[1,n]否则输出sum[n]-f[1,n]

0

527971925 LV 10 @ 2009-10-19 15:06:11

写了个记忆化....然后糊里糊涂的通过了......

---|---|---|---|---|---|---|---|---|---|---|

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 9ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

var n,first,t:longint;a:array[0..2000]of longint;

f:array[0..2000,0..2000,boolean]of longint;

function find(s,t:longint;r:boolean):longint;

var h1,h2:longint;

begin

if fh2 then

begin

f:=h1;

f:=f;

end

else

begin

f:=h2;

f:=f;

end;

end;

end;

find:=f;

end;

procedure init;

var i:longint;

begin

readln(n);

readln(first);

for i:=1 to n do read(a[i]);

fillchar(f,sizeof(f),250);

end;

begin

while not(eof) do

begin

init;

t:=find(1,n,true);

if first=1 then writeln(f[1,n,true]) else writeln(f[1,n,false]);

end;

end.

0

insomia LV 8 @ 2009-10-18 21:25:26

检查错误检查了n久...才发现原来数据n

0

augur_1990 LV 4 @ 2009-10-15 19:27:28

const

　　maxn=2000;

var

　　queue:array[1..maxn+10] of integer;

　　f:array[1..maxn,1..maxn+10] of integer;

　　sum:array[1..maxn,1..maxn+10] of integer;

　　n:integer;

procedure init;

var

　　i:integer;

begin

　　assign(input,'game1.in');reset(input);

　　readln(n);

　　for i:=1 to n do

　　　　begin

　　　　　　read(queue[i]);

　　　　　　sum:=queue[i];

　　　　　　f:=queue[i];

　　　　end;

　　close(input);

end;

function max(x,y:integer):integer;

begin

　　if x>y then exit(x)

　　else exit(y);

end;

procedure dp;

var

　　i,j:integer;

begin

　　for i:=n-1 downto 1 do

　　　　for j:=i+1 to n do

　　　　　　begin

　　　　　　　　sum:=sum+queue[j];

　　　　　　　　f:=max(sum+queue[i]-f,sum+queue[j]-f);

　　　　　　end;

　　assign(output,'game1.out');rewrite(output);

　　writeln(f[1,n],' ',sum[1,n]-f[1,n]);

　　close(output);

end;

begin

　　init;

　　dp;

end.

0

yzl609271536 LV 10 @ 2009-10-04 19:31:46

编译通过...

├ 测试数据 01：答案正确... 72ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 88ms

├ 测试数据 04：答案正确... 56ms

├ 测试数据 05：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：328ms

seekeof 居然不能用

交了 N次就是找不到错误

。。。。瀑布汗

0

陈亮宇 LV 10 @ 2009-10-04 13:38:21

while not eof do

begin

readln(n);

readln(kind);

for i:=1 to n do

begin

read(a[i]);

sum[i]:=sum+a[i];

f:=a[i];

end;

readln;

for l:=1 to n-1 do

for i:=1 to n-l do

begin

j:=i+l;

f:=max(sum[j]-sum-f,sum[j]-sum-f);

end;

if kind=0 then writeln(sum[n]-f[1,n]) else writeln(f[1,n]);

end;

0

飘の★ LV 10 @ 2009-09-25 23:13:03

神奇啊- -

一样的程序6k评测居然出现-1号错误

puppy就ac了

0

三代水影·游 LV 8 @ 2009-09-22 17:58:03

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

秒杀，庆祝一下。。

虽然有些水了，但也是一道比较经典的题，建议大家都认真AC掉。

for i:=1 to n do

sum[i]:=s+a[i];(注意数组开到0)

f:=max(f+a[i],f+a[j]);

f:=sum[j]-sum-f;

主程序就是这个了，这个转移方程让我想起了重庆省选的一道题。。

0

zgx LV 10 @ 2009-08-21 19:02:37

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

水题,

以下是动了手脚的程序：

program vijos1202;

var

sum,a,i:array[0..2111]of longint;

n,j,k:longint;

f:array[0..2111,0..2100,0..1]of longint;

function max(a,b:longint):longint;

begin

if a>b then exit(a) else exit(b);

end;

begin

readln(n);

readln(w);

for i:=1 to n do begin

read(a[i]);

sum[i]:=sum+a[i];

end;

for i:=1 to n do f:=a[i];

for k:=2 to n do

for i:=1 to n-k+1 do begin

j:=i+k-1;

f:=max(f+a[i],f+a[j]);

f:=sum[j]-sum-f;

end;

writeln(f[1,n,ww]);

end.

0

cass6 LV 9 @ 2009-08-15 21:50:47

f[j,i,1]:=max(f[j,i-1,2]+a[i],f[j+1,i,2]+a[j]);(小X先取)

f[j,i,2]:=t[i]-t[j-1]-f[j,i,1];(小X后取)

t[i]为1到i的和。

0

wzc1995 LV 10 @ 2009-08-15 17:47:00

解题报告

问题描述:

给出一个有n个数序列Q1,Q2,Q3...Qn,做一个博弈问题.

两人轮流重序列的两端取走一个数,在第二个人以最佳策略取数的情况下求第一个人取数的和的最大值.

问题分析:

两个人都以最佳策略取数,那么这个最佳策略就是一个一个最优解,考虑有n-2个数的序列,它的最优解为x,给这个序列再加上2个数,Qn-1,Qn,取这两个数的较大者加上x,就是一个新的最优解.反过来说,每个最优解,它减去序列中的一个数,都是另一种情况的最优解,所以最优子结构得证.

一个最优解可以加上数变成新的最优解,所以重叠子问题得证.可以用动态规划求解.

符号及变量说明:

记Q为数的序列,Qi为序列中第i个数.

记sum(i,j)为序列中第i个数到第j个数的和.

记f(i,j)为序列中由i开始到第j个数按照游戏规则能取得到的最大值.

模型的建立:

设得到一个子序列Qi,Qi+1,Qi+2,...,Qj-2,Qj-1,Qj;

由于后一个人按最佳策略取数,所以他必将取一个最大值f(i+1,j)或f(i,j-1),那么此时取数的人以后取得的数将是sum(i+1,j)-f(i+1,j)或是sum(i,j-1)-f(i,j-1),此时取数的人按最佳策略取数,他会取Qi或者Qj使得sum(i+1,j)-f(i+1,j)+Qi和sum(i,j-1)-f(i,j-1)+Qj二者能有较大值.这样从游戏的结束向游戏的开始推,可以得到总的最优解.

模型的求解:

显然,f(i,i)=sum(i,i)=Qi;这可以作为边界条件.

for i←n-1 downto 1 do

for j←i+1 to n do

begin

sum(i,j)←sum(i,j-1)+Qj

f←max{sum(i+1,j)+Qi-f(i+1,j),sum(i,j-1)+Qj-f(i,j-1)}

end;

Pascal参考程序：

const

maxn=2000;

var

queue:array[1..maxn+10] of integer;

f:array[1..maxn,1..maxn+10] of integer;

sum:array[1..maxn,1..maxn+10] of integer;

n:integer;

procedure init;

var

i:integer;

begin

assign(input,'game1.in');reset(input);

readln(n);

for i:=1 to n do

begin

read(queue[i]);

sum:=queue[i];

f:=queue[i];

end;

close(input);

end;

function max(x,y:integer):integer;

begin

if x>y then exit(x)

else exit(y);

end;

procedure dp;

var

i,j:integer;

begin

for i:=n-1 downto 1 do

for j:=i+1 to n do

begin

sum:=sum+queue[j];

f:=max(sum+queue[i]-f,sum+queue[j]-f);

end;

assign(output,'game1.out');rewrite(output);

writeln(f[1,n],' ',sum[1,n]-f[1,n]);

close(output);

end;

begin

init;

dp;

end.

C++参考程序：

#include

using namespace std;

int q[2010],sum[2010][2010],f[2010][2010],i,j,n,begin;

int main()

{

cin >> n;

cin >> begin;

for(i=1;i> q[i];

sum[i][i]=q[i];

f[i][i]=q[i];

}

for(i=n-1;i>=1;i--)

for(j=i+1;j

0

Amita LV 8 @ 2009-08-14 17:24:16

一开始想简单了不能按照奇数位和偶数位来算那样只能计算出能否有必胜的决策TT

0

重生的宁 LV 9 @ 2009-08-14 09:52:54

f(i)=sum(i)-min(f(i),f(i+1))

把前面大牛的方程改成这样，在空间上就可以实现降维了

时间复杂度O(n^2)空间复杂度O(n)没有必要使用记忆化了

附“参考”程序：

program P1202;

var

f,sum,num:array[0..2000]of longint;

n,i,j,a,b:longint;

function min(c,d:longint):longint;

begin

if c

0

Matt LV 10 @ 2009-08-11 18:36:52

编译通过...

├ 测试数据 01：答案错误...

　├ Hint: loalnv好可爱哦..

...

算作没一次AC的惩罚

500th AC！！

题解

65 条题解

Selection

信息

状态

开发

支持

题解

65 条题解

Selection

信息

状态

开发

支持

还没有账户？

登录