95 条题解
-
0
pRoevollove LV 9 @ 2009-03-11 15:36:15
啥优化也没加
1100ms暴力过 -
0
我把背包九讲再这里贴一下啦。。。
求次优解、第K优解
对于求次优解、第K优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，那么求次优解往往可以相同的复杂度解决，第K优解则比求最优解的复杂度上多一个系数K。
其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。
首先看01背包求最优解的状态转移方程：f[i][v]=max{f[v],f[v-c[i]]+w[i]}。如果要求第K优解，那么状态f[i][v]就应该是一个大小为K的数组f[i][v][1..K]。其中f[i][v][k]表示前i个物品、背包大小为v时，第k优解的值。“f[i][v]是一个大小为K的数组”这一句，熟悉C语言的同学可能比较好理解，或者也可以简单地理解为在原来的方程中加了一维。显然f[i][v][1..K]这K个数是由大到小排列的，所以我们把它认为是一个有序队列。
然后原方程就可以解释为：f[i][v]这个有序队列是由f[v]和f[v-c[i]]+w[i]这两个有序队列合并得到的。有序队列f[v]即f[v][1..K]，f[v-c[i]]+w[i]则理解为在f[v-c[i]][1..K]的每个数上加上w[i]后得到的有序队列。合并这两个有序队列并将结果的前K项储存到f[i][v][1..K]中的复杂度是O(K)。最后的答案是f[N][V][K]。总的复杂度是O(VNK)。
为什么这个方法正确呢？实际上，一个正确的状态转移方程的求解过程遍历了所有可用的策略，也就覆盖了问题的所有方案。只不过由于是求最优解，所以其它在任何一个策略上达不到最优的方案都被忽略了。如果把每个状态表示成一个大小为K的数组，并在这个数组中有序的保存该状态可取到的前K个最优值。那么，对于任两个状态的max运算等价于两个由大到小的有序队列的合并。
另外还要注意题目对于“第K优解”的定义，将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者，则维护有序队列时要保证队列里的数没有重复的。 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 9ms
├ 测试数据 07：答案正确... 9ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：18ms
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--
数据有序化下+双队列维护,就是速度快啊 呵呵*.*)) -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 181ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 493ms
├ 测试数据 07：答案正确... 618ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：1292ms
注意的问题是：
对于动规的每一个状态(重量j)选用时，要判断能否达到！！！
设h[0..5000]数组，初始时：h[0]:=true;其他为false。
判断能否到达为：h[j]:=h[j] or h[j-w[i]](j>=w[i]时)
若h[j]=true，则可以更新。 -
0
foreverwind LV 3 @ 2008-11-06 14:17:02
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 88ms
├ 测试数据 07：答案正确... 88ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：176ms
第80道ac 庆祝．．．． -
0
czz5242199 LV 9 @ 2008-11-05 22:10:22
标程：编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 9ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 243ms
├ 测试数据 07：答案正确... 337ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：589msvar n,num,vv:longint;
w,v:array[0..200] of longint;
f:array[0.. 5000,0..40] of longint;
t1,t2:array[0..40] of longint;
procedure init;
var i,k:longint;
begin
readln(num,vv,n);
for i:=1 to n do readln(w[i],v[i]);
end;
procedure main;
var i,k,j,c1,c2,c3,q1,q2:longint;
begin
fillchar(f,sizeof(f),0); f[0,0]:=1;
for i:=1 to n do
for k:=vv downto w[i] do
if f[k-w[i],0]0 then
begin
c1:=f[k,0]; c2:=f[k-w[i],0];
c3:=c1+c2; if c3>num then c3:=num;
q1:=1; q2:=1;
t1:=f[k]; t2:=f[k-w[i]];
for j:=1 to c2 do t2[j]:=t2[j]+v[i];
for j:=1 to c3 do
if (t1[q1]>t2[q2]) or (q2>c2) then begin f[k,j]:=t1[q1]; inc(q1); end
else begin f[k,j]:=t2[q2]; inc(q2); end;
f[k,0]:=c3;
end;
j:=0;
for i:=1 to num do
inc(j,f[vv,i]);
writeln(j);
end;
begin
init;
main;
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 56ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 416ms
├ 测试数据 07：答案正确... 806ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：1278ms好慢...
但是给大家讲个笑话：话说我前两次提交都打错了个变量，居然一次40，一次60！
话说我第一次提交连样例都没测就交了... -
0
按价值排序快
按性价比排序慢
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 462ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：运行超时...
├ 测试数据 07：运行超时...
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 150ms
├ 测试数据 07：答案正确... 338ms -
0
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 462ms
├ 测试数据 07：答案正确... 150ms一次AC。。但是有点慢。。
对于这句话“每个人的背包都要放满”不要想太多，队列合并与原来背包不同的地方就是做完之后有数字的地方就是可以到达的。
前提是在做的时候加句判断，如果这个状态不能到达，就不要用这个状态去更新其他的状态。 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 166ms
├ 测试数据 07：答案正确... 291ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：457ms搞了N多次 终于AC了
纪念一下program p1412;
type nt=array[0..5000,0..41]of longint;
var p,wh,code,h,i,j,k,m,n:longint;
f:nt;
S:ARRAY[0..5000]OF LONGINT;
v,w:array[0..201]of longint;
KK:EXTENDED;
VALUE:ARRAY[0..201]OF EXTENDED;
begin
readln(p,m,n);
for i:=1 to n do
readln(v[i],w[i]);
FOR I:=1 TO N DO
VALUE:=W/V;
FOR I:=1 TO N-1 DO
FOR J:=I+1 TO N DO
IF VALUEf[i+v[k],p] then
begin
if S[i+v[k]]
pRoevollove
LV 9
@ 2009-03-11 15:36:15
