题解 - Vijos

1

#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

fjxmlhx LV 10 @ 15 年前

好题！

明确下题意：

按顺序给出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

Spectre LV 10 @ 7 年前

#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

308454 LV 10 @ 9 年前

嗯，就是一个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

午后奶茶 LV 8 @ 15 年前

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

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

0

Procedure LV 8 @ 15 年前

总共提交了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;

mli @ 9 年前

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

0

blacksnow LV 10 @ 15 年前

USACO3.4.4

0

这号是马甲 LV 8 @ 15 年前

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

darin LV 10 @ 15 年前

很丑的程序啊。。。。。但是因为没有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

robin-lun LV 7 @ 15 年前

编译通过...

├ 测试数据 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

xuzhendong28 LV 5 @ 15 年前

what's th mean?

0

sxx1995 LV 5 @ 15 年前

can't怎么输出

0

陈亮宇 LV 10 @ 15 年前

提交　　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

Lemon tree LV 8 @ 15 年前

语文…………

0

Red-Zero LV 9 @ 15 年前

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

0

LP.Fighting LV 10 @ 15 年前

用downto 可以不用滚动

注意=的情况

0

雨中的风筝 LV 10 @ 15 年前

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

0

BABO LV 8 @ 15 年前

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

还蛮漂亮的.

0

yzl609271536 LV 10 @ 15 年前

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

时间好弱

0

M36_slugger LV 10 @ 15 年前

刚开始看不懂，但看懂了就很简单了，这就是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

题解

41 条题解

NightElf

信息

状态

开发

支持

题解

41 条题解

NightElf

信息

状态

开发

支持

还没有账户？

登录