01背包 模板题
Program dd;
const
maxn=1000;
maxv=100000;
minv=-100000;
NULL=-2139062144;
var
n,i,j,ans,p,np:longint;
ts,tf:array[1..maxn] of longint;
f:array[0..1,minv..maxv] of longint;
function max(a,b:longint):longint;
begin
if a<b then exit(b) else exit(a);
end;
begin
read(n);
for i:=1 to n do read(ts[i],tf[i]);
fillchar(f,sizeof(f),128);
f[0,0]:=0;
for i:=1 to n do
begin
p:=i mod 2;
fillchar(f[p],sizeof(f[p]),128);
np:=(p+1) mod 2;
for j:=maxv downto minv do
begin
f[p,j]:=f[np,j];
if (minv<=j-ts[i]) and (j-ts[i]<=maxv) then
if (f[np,j-ts[i]]<>NULL) then
f[p,j]:=max(f[p,j],f[np,j-ts[i]]+tf[i]);
end;
end;
ans:=0;
for i:=0 to maxv do
if (f[n mod 2,i]>=0) and (ans<f[n mod 2,i]+i) then ans:=f[n mod 2,i]+i;
writeln(ans);
end.
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1745671
NULL 博文链接:https://128kj.iteye.com/blog/1757060
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1750462
NULL 博文链接:https://128kj.iteye.com/blog/1744222
晒代码之二——多重背包(POJ1276)
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
西北工业大学POJ试题C++答案代码+课程设计
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
北大POJ初级-简单搜索 解题报告+AC代码
西工大POJ习题第五季,数组这类的代码,有截图
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
动态规划 01背包问题 POJ3624可以AC
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1159-Palindrome 解题报告+AC代码