题解

41 条题解

  • 1
    @ 2020-11-16 16:52:13
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <deque>
    using namespace std;
    
    namespace dts
    {
        const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
        
        int n,t,a[3000],day[3001],eng[3001];
        
        void main()
        {
            scanf("%d%d",&n,&t);
            for (int i=0;i<n;i++)
                scanf("%d",&a[i]);
            memset(day,oo_max,sizeof(day));
            memset(eng,0,sizeof(eng));
            day[0]=0;
            for (int i=0;i<n;i++)
                if (a[i]<120)
                    for (int j=t;j>=1;j--)
                    {
                        int tmpday=day[j-1],tmpeng=eng[j-1];
                        if (tmpeng>a[i])
                            tmpeng-=a[i];
                        else
                            tmpday++,tmpeng=120-a[i];
                        if (tmpday<day[j]||(tmpday==day[j]&&tmpeng>eng[j]))
                            day[j]=tmpday,eng[j]=tmpeng;
                    }
            if (day[t]<oo_max)
                printf("%d\n",day[t]);
            else
                printf("You can't do it.\n");
        }
    }
    
    int main()
    {
        dts::main();
    }
    
  • 1
    @ 2009-09-13 11:28:03

    好题!

    明确下题意:

    按顺序给出N个能量,你可以选择接受或不接受,然后选择睡觉或不睡觉,睡觉则恢复120体力,然后再选择接受或不接受..题目即求在体力恒>0的情况下接受k个能量的最少睡觉天数。

    令g[i][j]表示后i个能量,初始体力值120,吸收j个能量需要的最少时间。

    f[i][j]表示表示后i个能量,吸收j个能量,天数=g[i][j]时最小的初始体力值。

    考虑求g[i][j]:

    若选择不接受能量后不睡觉,则转移至g[j],代价为0.

    若选择接受能量后睡觉,则需满足a[i]

  • 0
    @ 2018-01-28 11:55:07
    #include<iostream>
    using namespace std;
    
    #define MAXN 3005
    #define INF 10000000
    
    int n,k;
    struct node
    {
        int day,energy;
    
        bool operator < (node& x)
        {
            return (day<x.day) || (day==x.day && energy>x.energy);
        }
    }f[MAXN];
    
    int main()
    {
        ios::sync_with_stdio(0);
        cin >>n>>k;
    
        f[0].day=0;f[0].energy=0;
        for(int i=1;i<=k;i++)
        {
            f[i].day=INF,
            f[i].energy=0;
        }
    
        int x;
        node t;
        for(int i=1;i<=n;i++)
        {
            cin >>x;
            if(x>=120) continue;
            for(int j=k;j>=1;j--)
            {
                t=f[j-1];
                if(t.energy>x)
                {
                    t.energy-=x;
                }
                else
                {
                    t.day++;
                    t.energy=120-x;
                }
                if(t<f[j]) f[j]=t;
            }
        }
    
        if(f[k].day<INF) cout <<f[k].day<<endl;
        else cout <<"You can't do it."<<endl;
    
        return 0;
    }
    
    
  • 0
    @ 2015-06-28 14:58:13

    嗯,就是一个0-1背包
    f[i,j].day表示前i个能量选了j个最少的天数
    f[i,j].energy表示前i个能量选了j个在第f[i,j].day天最多还剩下f[i,j].energy点的能量
    const maxe=120;
    maxk=3000;
    inf=1000000000;
    type node=record
    day,ene:longint;
    end;
    var n,k,a,i,j:longint;
    f:array[0..maxk] of node;
    t:node;
    begin
    readln(n,k);
    f[0].day:=1;
    f[0].ene:=maxe;
    for i:=1 to k do begin
    f[i].day:=inf;
    f[i].ene:=0;
    end;
    for i:=1 to n do begin
    read(a);
    if a>=maxe then continue;
    for j:=k downto 1 do begin
    t:=f[j-1];
    if t.ene>a then dec(t.ene,a) else begin
    inc(t.day);
    t.ene:=maxe-a;
    end;
    if (t.day<f[j].day)or((t.day=f[j].day)and(t.ene>f[j].ene)) then f[j]:=t;
    end;
    end;
    writeln(f[k].day);
    end.

  • 0
    @ 2009-10-23 14:11:41

    注意了!前一天剩余的体力不能继承。

    也就是说睡觉只是把体力补充回120,并不是把体力加120。

  • 0
    @ 2009-10-20 21:25:54

    总共提交了3次,今天晚上真是卡啊。

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    这道题的语文理解很吃力,每天最多只能获得1个单位能量,并且如果不得到能量就可以把体力加到120.感谢楼下大牛的提示。

    动态转移方程在程序中,二维的动归要用滚动数组做!

    以下是核心代码

    for i:=1 to n do

    begin

    T:=i mod 2; T1:=(i-1) mod 2;

    if i>1 then f[T]:=f[T1];

    for j:=i downto 1 do

    begin

    if (a[i]>=120) or (f[t1,j-1,0]=maxlongint) then continue;

    if f[T1,j-1,1]a[i] then {当前体力够做}

    begin

    d:=f[T1,j-1,0];

    r:=f[T1,j-1,1]-a[i];

    end;

    {天数更少,或天数相同但体力更多 更新}

    if (df[T,j,1])) then

    begin

    f[T,j,0]:=d;

    f[T,j,1]:=r;

    end;

    end;

    end;

    • @ 2016-03-22 20:34:09

      为什么
      T:=i mod 2; T1:=(i-1) mod 2;
      if i>1 then f[T]:=f[T1];
      for j:=i downto 1
      这样

  • 0
    @ 2009-10-10 21:48:17

    USACO3.4.4

  • 0
    @ 2009-10-10 19:04:01

    var

    n,t,a,b:longint;

    g,h:array[0..3000] of longint;

    k:array[0..3000] of longint;

    procedure gs(a,b,c:longint; var d,e:longint);

    var

    ta,tb:longint;

    begin

    if b+c

  • 0
    @ 2009-09-27 22:18:23

    很丑的程序啊。。。。。但是因为没有pascal程序我就小贴一下拉,,,,,

    我弱啊。错好多次。。。。。不等号都打错。。。。题解ls很详细了哦···

    program vijos1648;

    var j,n,k,i,max : longint;

    a : array[1..3000] of longint;

    f,g : array[0..3002] of integer;

    begin

    readln(n,k);

    for i := 1 to n do

    read(a[i]);

    for j := 0 to n + 1 do

    g[j] := 4000;

    max := g[1];

    g[0] := 0;

    for i := n downto 1 do

    for j := k downto 1 do

    begin

    if (a[i]>=120) or (g[j-1] = max) then continue;

    if ((g[j] > g[j-1]+1) or

    (g[j] = g[j-1]+1) and (f[j] > a[i])) then

    begin

    g[j] := g[j-1] + 1;

    f[j] := a[i];

    end;

    if (f[j-1]+a[i]

  • 0
    @ 2009-09-27 21:01:21

    编译通过...

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

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

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

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

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

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

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

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

    for (int i = 1; i 0; get--)

    {

    r = f[get-1].rest - num[i];

    if (r > 0 && f[get-1].day ?= r;

    else f[get].rest = r;

    f[get].day = f[get-1].day;

    }

    if (r

  • 0
    @ 2009-09-21 13:55:01

    what's th mean?

  • 0
    @ 2009-09-20 20:32:09

    can't怎么输出

  • 0
    @ 2009-09-19 18:05:47

    提交   666次

    63/200(31%)

    感觉和集装箱问题一样

    编译通过...

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

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

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

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

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

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

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

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

  • 0
    @ 2009-09-16 13:17:14

    语文…………

  • 0
    @ 2009-09-16 10:58:09

    类似装箱问题,不过需要注意一下,当f[i]=f的时候就要尽量使体力花费小

  • 0
    @ 2009-09-15 18:49:31

    用downto 可以不用滚动

    注意=的情况

  • 0
    @ 2009-09-15 17:33:54

    没有滚动数组的话,要用integer。。。

  • 0
    @ 2009-09-15 00:39:41

    编译通过...

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

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

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

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

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

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 9ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

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

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

    还蛮漂亮的.

  • 0
    @ 2009-09-14 21:58:32

    编译通过...

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

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

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

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

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

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 25ms

    ├ 测试数据 09:答案正确... 0ms

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

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

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

    时间好弱

  • 0
    @ 2009-09-14 21:33:49

    刚开始看不懂,但看懂了就很简单了,这就是01背包嘛~~~~~~~~~~~~~~

    只不过原来记一个值改成了两个而已,很简单的,但是居然下标打反了…………

    核心代码

    for(i=1;i0;j--)

    {//刚开始下面所有的c[i]都写成了c[j],- -!

    if(c[i]>=120||f[j-1].day==inf) continue;

    if(f[j-1].rest

信息

ID
1648
难度
7
分类
动态规划 点击显示
标签
(无)
递交数
1117
已通过
206
通过率
18%
被复制
2
上传者