题解

65 条题解

  • 4
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2009-11-07 16:13:19

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

  • 0
    @ 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
    @ 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
    @ 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
    @ 2009-10-18 21:25:26

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

  • 0
    @ 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
    @ 2009-10-04 19:31:46

    编译通过...

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

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

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

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

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

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

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

    seekeof 居然不能用

    交了 N次 就是找不到错误

    。。。。瀑布汗

  • 0
    @ 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
    @ 2009-09-25 23:13:03

    神奇啊- -

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

    puppy就ac了

  • 0
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2009-08-14 17:24:16

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

  • 0
    @ 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
    @ 2009-08-11 18:36:52

    编译通过...

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

     ├ Hint: loalnv好可爱哦..

    ...

    算作没一次AC的惩罚

    500th AC!!

信息

ID
1202
难度
5
分类
动态规划 点击显示
标签
(无)
递交数
909
已通过
326
通过率
36%
被复制
4
上传者