41 条题解
-
1Sky1231 (sky1231) LV 10 @ 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(); }
-
12009-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] -
02018-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; }
-
02015-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. -
02009-10-23 14:11:41@
注意了!前一天剩余的体力不能继承。
也就是说睡觉只是把体力补充回120,并不是把体力加120。 -
02009-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; -
02009-10-10 21:48:17@
USACO3.4.4
-
02009-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 -
02009-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] -
02009-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 有效耗时:0msfor (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 -
02009-09-21 13:55:01@
what's th mean?
-
02009-09-20 20:32:09@
can't怎么输出
-
02009-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 -
02009-09-16 13:17:14@
语文…………
-
02009-09-16 10:58:09@
类似装箱问题,不过需要注意一下,当f[i]=f的时候就要尽量使体力花费小
-
02009-09-15 18:49:31@
用downto 可以不用滚动
注意=的情况 -
02009-09-15 17:33:54@
没有滚动数组的话,要用integer。。。
-
02009-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还蛮漂亮的.
-
02009-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时间好弱
-
02009-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