又找到一道01背包

program p1407;

type x=record

z,c,v:longint;

end;

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

a:array[1..10000] of x;

b,f:array[0..10000] of longint;

g:array[0..10000] of longint;

begin

readln(n,m);

for i:=1 to 3 do

readln(a[i].z,a[i].c,a[i].v);

for i:=1 to n do

begin

readln(b[i],k);

for j:=1 to 3 do if a[j].z=k then begin f[i]:=a[j].c*b[i]; inc(b[i],a[j].v*b[i]); break; end;

for j:=m downto b[i] do

if g[j-b[i]]+f[i]>g[j] then g[j]:=g[j-b[i]]+f[i];

end;

writeln(g[m]);

end.

我讨厌这个文字游戏！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

const filename='p1407';

var

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

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

v,z:array[1..100]of longint;

f:array[0..8000]of longint;

function max(x,y:longint):longint;

begin if x>y then exit(x);exit(y);end;

begin

assign(input,filename+'.in');reset(input);

assign(output,filename+'.out');rewrite(output);

readln(n,m);

for i:=1 to 3 do

read(a[i],b[i],c[i]);

for i:=1 to n do

begin

read(v[i],k);

for j:=1 to 3 do if k=a[j] then z[i]:=j;

k:=z[i];

z[i]:=v[i]*b[k];

v[i]:=v[i]+v[i]*c[k];

end;

for i:=1 to n do

for j:=m downto v[i] do

f[j]:=max(f[j],f[j-v[i]]+z[i]);

writeln(f[m]);

close(input);close(output);

end.

看了半个小时没有看懂。。。。。

这题考的不是背包

是语文。。。

水题出成这个样子也很不容易啊……

楼下340508965讲得很好，作为oier，语文功底必须要有，否则怎么做水题！

程序22行。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

还以为是完全背包，结果是0/1的

这题什么意思？

每一体积布上绣的这种花纹的体积v[z]（0

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

这么水的水题 我当初硬是没做出来

现在才发现 原来当初我认为 V=V布*V花

实际上 是V=V布+V布*V花

做了N道水题之后 总结出了如下规律：

水题想要摆脱水题这个不好的称号 但是本质上限定了它是水题 所以它从其他方面着手

1.题意不清---|-题目的描述经常很含糊，不知所以然，要不就是讲一半藏一半

简直比语文考试还累人

2.数据范围---|-最讨厌那些明明标起来多少多少但数据实际上却扩大了的

MS这种情况很泛滥 很严重

3.最优答案---|-有时候DP可能两种方案都可以 我们经常都选择前者，而答案可能选后者

4.输入输出格式不标准

比如要输入： 它可能输入：

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 0

要你输出空格 但有些不能+空格的地方它不告诉你

5.特殊数据

经常拿一些特殊的例子给你 让你程序崩溃...

6......

好了一时想不起来其他的了 有的话 最好楼上接着指出来啊

精简才是王道啊( ⊙ o ⊙ )！

---|---|---|---|---|---|---|---|-晒程序啊---|---|---|---|---|---|---|---|---|---|---|-

var n,m,i,k,vs,v,c:longint;

vt,ct,f:array[0..37000] of longint;

begin

readln(n,m);

for i:=1 to 3 do begin

readln(k,c,v);

ct[k]:=c; vt[k]:=v;

end;

for i:=1 to n do begin

readln(v,k);

c:=v*ct[k]; v:=v+v*vt[k];

for vs:=m downto v do

if f[vs]

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

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

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

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

├ 测试数据 05：运行时错误...|错误号: 5

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

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

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

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

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

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

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

Unaccepted 有效得分：91 有效耗时：0ms

靠 第一次有这么怪异的得分！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

program fh;

var a,b:array[1..3,1..3]of longint;

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

f:array[1..300000]of longint;

i,j,n,m:longint;

begin

readln(n,m);

for i:=1 to 3 do

begin

for j:=1 to 3 do

read(a);

readln;

end;

for i:=1 to n do

readln(c,c);

for i:=1 to 3 do

for j:=1 to n do

if a=c[j,2] then

begin

c[j,3]:=c[j,1]*(1+a);

c[j,4]:=c[j,1]*a;

end;

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

for i:=1 to n do

for j:=m downto c do

if f[j]

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

program p1407;

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

f:array[0..8000] of longint;

i,j,k,l,m,n,sum,r,s,t,z:longint;

function max(x,y:longint):longint;

begin if x>y then max:=x else max:=y;end;

begin

readln(n,m);

for i:=1 to 3 do

begin readln(z,c[z],b[z]);end;

for i:=1 to n do

begin readln(r,s);v[i]:=r+r*b;a[i]:=r*c;end;

for i:=1 to n do

for j:=m downto v[i] do

f[j]:=max(f[j],f[j-v[i]]+a[i]);

writeln(f[m]);

end.

当时对着题目郁闷了很久……原来就是个01背包加个麻烦的处理哈……

这种题目还用了四次提交我真是弱的可以……

此题就是要你明白

对于某个物品（花是相对应的花），它的两个属性V,W

V=V布+V布*V花

W=V布*W花。。。

V是体积 W是价值

就是关于V W的赤裸裸的01背包。

“注意对于每匹布的体积应该是该布的体积+该布体积*对应花的体积”

我也是这里错了

题目意思不清楚。。看了ls牛的讲解才理解题目意思。。

看不懂题……

总算把题目看懂了。好BT啊

不要忘了布匹本身的体积

样例很渣的哟～

其实数据没有那么大.....