题解 - Vijos

0

Nightingalelyy LV 10 @ 2017-03-31 13:06:46

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
#include <string>
#include <map>
#include <ciso646>
#include <stack>
#include <cstdlib>
using namespace std;
const int maxn = 1000000;


int dp[10001][10001];
int t[10001][10001];
int rp[10001];
int tim[10001];
int w[10001];

int n, m, i, j, k, l, r;
int main()
{
    scanf("%d", &n);
    for (i = 1;i <= n;i++)
        scanf("%d%d%d", &w[i], &rp[i], &tim[i]);

    scanf("%d%d", &m, &r);
      
    
    dp[0][0] = 0;
    dp[m][r] = 0;

    for(i=1;i<=n;i++)
        for(j=r;j>=rp[i];j--)
            for (k = m;k >= w[i];k--)
                if (dp[j][k] <= dp[j - rp[i]][k - w[i]] + 1)
            {
                    if (dp[j][k] < dp[j - rp[i]][k - w[i]] + 1)
                    {
                        dp[j][k] = dp[j - rp[i]][k - w[i]] + 1;
                        t[j][k] = t[j - rp[i]][k - w[i]] + tim[i];
                    }
                    else
                        t[j][k] = min(t[j][k], t[j - rp[i]][k - w[i]] + tim[i]);
            }
    
    printf("%d\n", t[r][m]);

    system("pause");
    return 0;
}

两层的01背包，dp记录泡到的人数，t[][]记录在r的rp值，m的钱数下能泡到最多妹子的最短时间
dp[][]记录在r，m下能泡到的最多的妹子数

0

TenderRun LV 10 @ 2015-08-21 18:41:51

记录信息
评测状态 Accepted
题目 P1544 GF
递交时间 2015-08-21 18:40:03
代码语言 C++
评测机 Jtwd2
消耗时间 15 ms
消耗内存 1612 KiB
评测时间 2015-08-21 18:40:04
评测结果
编译成功

foo.cpp: In function 'int main()':
foo.cpp:20:130: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
测试数据 #0: Accepted, time = 0 ms, mem = 1604 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1604 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1604 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1608 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1608 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 1612 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1600 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1600 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1604 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1608 KiB, score = 10
Accepted, time = 15 ms, mem = 1612 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
using namespace std;
int MM[310][310][3];
int rmb[310];
int rp[310];
int time[310];
int main()
{
int n,maxans=-1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&rmb[i],&rp[i],&time[i]);
int r,p;
scanf("%d%d",&r,&p);

for(int i=1;i<=n;i++)
for(int j=r;j>=rmb[i];j--)
for(int k=p;k>=rp[i];k--)
{
if(MM[j][k][1]<MM[j-rmb[i]][k-rp[i]][1]+1||MM[j][k][1]==MM[j-rmb[i]][k-rp[i]][1]+1&&MM[j-rmb[i]][k-rp[i]][2]+time[i]<MM[j][k][2])
{
MM[j][k][1]=MM[j-rmb[i]][k-rp[i]][1]+1;
MM[j][k][2]=MM[j-rmb[i]][k-rp[i]][2]+time[i];
if(maxans<MM[j][k][1])
maxans=MM[j][k][1];
}

}
int minans=1000000000;
for(int j=r;j;j--)
for(int k=p;k;k--)
{
if(MM[j][k][1]==maxans)
{
if(minans>MM[j][k][2])
minans=MM[j][k][2];
}
}
printf("%d",minans);
}

0

1996yikai LV 7 @ 2013-11-08 21:25:52

纪念AC20 变种01背包

0

无语中！ LV 8 @ 2012-10-29 13:30:40

GF

VijosNT Mini 2.0.5.7 Special for Vijos

foo.pas(12,23) Warning: Variable "ans" does not seem to be initialized

foo.pas(15,30) Warning: Variable "timeans" does not seem to be initialized

├ 测试数据 01：答案正确... (75ms, 664KB)

├ 测试数据 02：答案正确... (0ms, 664KB)

├ 测试数据 03：答案正确... (0ms, 664KB)

├ 测试数据 04：答案正确... (754ms, 664KB)

├ 测试数据 05：答案正确... (680ms, 664KB)

├ 测试数据 06：答案正确... (668ms, 664KB)

├ 测试数据 07：答案正确... (680ms, 664KB)

├ 测试数据 08：答案正确... (762ms, 664KB)

├ 测试数据 09：答案正确... (598ms, 664KB)

├ 测试数据 10：答案正确... (0ms, 664KB)

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

Accepted / 100 / 4220ms / 664KB

view sourceprint?01 var

02 n,i,m,r,j,k:longint;

03 timeans,ans:array[0..101,0..101]of longint;

04 rmb,rp,time:array[1..100]of longint;

05 begin

06 readln(n);

07 for i:=1 to n do readln(rmb[i],rp[i],time[i]);

08 readln(m,r);

09 for i:=1 to n do

10 for j:=m downto rmb[i] do

11 for k:=r downto rp[i] do

12 if ans[j,k]timeans[j-rmb[i],k-rp[i]]+time[i] then

20 timeans[j,k]:=timeans[j-rmb[i],k-rp[i]]+time[i];

21 writeln(timeans[m,r]);

22 end.

0

石力铭 LV 8 @ 2010-04-14 14:40:07

不会……谁教教？

0

xudyh LV 10 @ 2010-04-12 16:59:47

program dyh(input,output);

var

maxv,maxg,n,i,j,k:longint;

f:packed array[0..400,0..400]of longint;

v,g,c:packed array[1..100]of longint;

begin

readln(n);

for i:=1 to n do

begin

readln(v[i],g[i],c[i]);

c[i]:=10000000-c[i];

end;

readln(maxv,maxg);

for i:=1 to n do

for j:=maxv downto v[i] do

for k:=maxg downto g[i] do

begin

if f[j,k]

0

芒果木瓜榴莲 LV 9 @ 2009-11-14 09:47:39

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

i,j,k,n,m,r:longint;

a,b,c:array[1..100]of longint;

f,t:array[0..100,0..100]of longint;

begin

readln(n);

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

readln(m,r);

for i:=1 to n do

for j:=m downto b[i] do

for k:=r downto c[i] do

if f[j,k]t[j-b[i],k-c[i]]+a[i])then

t[j,k]:=t[j-b[i],k-c[i]]+a[i];

writeln(t[m,r]);

end.

谁能具体讲一下动规的赋初值的问题？

0

lxyxyntt LV 6 @ 2009-11-10 15:50:40

program p1544;

var

dp:array[0..100,0..100]of longint;

tp:array[0..100,0..100]of longint;

rmb:array[1..100]of integer;

rp:array[1..100]of integer;

time:array[1..100]of integer;

p,m,r,t:longint;

n:integer;

i,j,k:integer;

begin

readln(n);

for i:=1 to n do readln(rmb[i],rp[i],time[i]);

readln(m,r);

//fillchar(dp,sizeof(dp),0);

for k:=1 to n do

for i:=m downto rmb[k] do

for j:=r downto rp[k] do

if dp[i-rmb[k],j-rp[k]]+1>dp then

begin

dp:=dp[i-rmb[k],j-rp[k]]+1;

tp:=tp[i-rmb[k],j-rp[k]]+time[k];

if ptp) then t:=tp;

end

else if (dp[i-rmb[k],j-rp[k]]+1=dp)and(tp>tp[i-rmb[k],j-rp[k]]+time[k]) then

begin

tp:=tp[i-rmb[k],j-rp[k]]+time[k];

if (p=dp)and(tp

0

578559967 LV 10 @ 2009-10-29 21:59:07

var

f :array[0..100,0..100,0..100]of longint;

i,j,k,l,mm,pp,n :longint;

m,p,t :array[0..100]of longint;

begin

readln(n);

for i:=1 to n do

readln(m[i],p[i],t[i]);

readln(mm,pp);

for i:=mm downto 0 do

for j:=pp downto 0 do

begin

for k:=1 to n do

f:=maxlongint;

f:=0;

end;

for i:=1 to n do

for j:=mm downto m[i] do

for k:=pp downto p[i] do

for l:=i downto 1 do

if f[j,k,l]-t[i]>f[j-m[i],k-p[i],l-1] then

f[j,k,l]:=f[j-m[i],k-p[i],l-1]+t[i];

for i:=n downto 0 do

if f[mm,pp,i]

0

honghaijie LV 9 @ 2009-10-24 09:01:08

什么是GF?？

0

beakham LV 8 @ 2009-10-22 22:33:21

太水~

0

RayXie LV 8 @ 2009-10-15 21:59:02

var

max,min:longint;

n,m,r:longint;

f,t:array[0..1001,0..1001]of longint;

rmb,rp,time:array[0..1001]of longint;

procedure init;

var

i:integer;

begin

readln(n);

for i:=1 to n do readln(rmb[i],rp[i],time[i]);

readln(m,r);

fillchar(f,sizeof(f),0);

fillchar(t,sizeof(t),0);

max:=0;

min:=maxlongint;

end;

procedure work;

var

k,i,j:longint;

begin

for k:=1 to n do

for i:=m downto rmb[k] do

for j:=r downto rp[k] do

begin

if f[i-rmb[k],j-rp[k]]+1>f then

begin

f:=f[i-rmb[k],j-rp[k]]+1;

t:=t[i-rmb[k],j-rp[k]]+time[k];

end

else if (f[i-rmb[k],j-rp[k]]+1=f)and(t[i-rmb[k],j-rp[k]]+time[k]max)or((f=max)and(t

0

22250 LV 8 @ 2009-09-24 15:49:57

一开始用的三维

f=max（f，f+1）;

发现三维的并不能优化到只用一个数组，但是看楼上的题解貌似可以，请教哇！！！！

这是我再开一个数组的方法。

f[j,k]:=max(f+1,f[j,k]) 这个是处理选MM数量以及选的哪些。

然后在开个数组 time[j,k] 记下时间。

循环很简单

DP的时候需要注意下 MM数一样的时候，取时间少的覆盖。

0

xfx LV 8 @ 2009-09-24 15:14:11

啊，好混蛋的题目描述~~~

0

汪小正 LV 8 @ 2009-09-20 12:02:23

详细讲解

可读性超强的程序

欢迎光临

http://wwzhwdwd.blog.163.com/blog/static/12815145020098200037649/

0

skykey LV 9 @ 2009-09-17 18:18:44

用滚动数组+背包DP

0

zhangyq987 LV 8 @ 2009-09-13 18:15:17

二维背包两次AC

var

n,i,j,p,z,k,m,r:longint;

rm,rp,ti:packed array[1..100]of integer;

t,f:packed array[0..100,0..100]of longint;

begin

readln(n);

for i:=1 to n do readln(rm[i],rp[i],ti[i]);

read(m,r);

for k:=1 to n do

for i:=m downto rm[k] do

for j:=r downto rp[k] do

if f[i-rm[k],j-rp[k]]+1>f then

begin

f:=f[i-rm[k],j-rp[k]]+1;

t:=t[i-rm[k],j-rp[k]]+ti[k];

if f>p then begin p:=f;z:=t;end;

if (f=p)and(tt[i-rm[k],j-rp[k]]+ti[k])

then

begin

t:=t[i-rm[k],j-rp[k]]+ti[k];

if (f=p)and(t

0

wzc1995 LV 10 @ 2009-09-05 23:41:05

二维背包的变异

0

lixiaomu3 LV 7 @ 2009-08-30 12:48:08

第266个通过

简单的DP

0

bi1_1 LV 9 @ 2009-08-22 19:09:39

真囧，少写一个BEGIN和END; 害的我去查数据

题解

50 条题解

GF

信息

状态

开发

支持

题解

50 条题解

GF

信息

状态

开发

支持

还没有账户？

登录