背包类DP
（1） 0/1背包
var
n,m,i,j:longint;
w,c:array[1..30] of longint; f:array[0..100000] of longint; function max(a,b:longint):longint; begin
if a>=b then exit(a) else exit(b); end; begin
readln(n,m);
for i:=1 to n do readln(w[i],c[i]); fillchar(f,sizeof(f),0); for i:=1 to n do
for j:=m downto w[i] do
f[j]:=max(f[j-w[i]]+c[i],f[j]);
writeln(f[m]); end.
（2） 完全背包 var
n,m,i,j:longint;
w,c:array[1..30] of longint; f:array[0..100000] of longint; function max(a,b:longint):longint; begin
if a>=b then exit(a) else exit(b); end; begin
readln(n,m);
for i:=1 to n do readln(w[i],c[i]); fillchar(f,sizeof(f),0); for i:=1 to n do
for j:=w[i] to m do
f[j]:=max(f[j-w[i]]+c[i],f[j]); writeln(f[m]); end.
(3)二维费用背包
3.２１
背景：潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让
潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？ 例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量： 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119
如果潜水员需要5升的氧和60升的氮则总重最小为249 （1，2或者4，5号气缸）。 你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。 【输入格式】
第一行有2整数t，a（1<=t<=21，1<=a<=79）。它们表示氧，氮各自需要的量。 第二行为整数n （1<=n<=1000）表示气缸的个数。
此后的n行，每行包括ti，ai，wi（1<=ti<=21，1<=ai<=79，1<=wi<=800）3整数。这些各自是：第i个气缸里的氧和氮的容量及汽缸重量。 【输出格式】
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值
var
f:array[0..21,0..79] of longint; i,j,k,n,t,a,j1,k1:longint;
ti,ai,w:array[1..1000] of longint; function min(a,b:longint):longint; begin
if a<=b then exit(a) else exit(b); end; begin
readln(t,a); readln(n);
fillchar(f,sizeof(f),$7f);
for i:=1 to n do readln(ti[i],ai[i],w[i]); f[0,0]:=0;
for i:=1 to n do
for j:=t downto 0 do for k:=a downto 0 do begin
if j+ti[i]>t then j1:=t else j1:=j+ti[i]; if k+ai[i]>a then k1:=a else k1:=k+ai[i]; f[j1,k1]:=min(f[j,k]+w[i],f[j1,k1]); end; writeln(f[t,a]); end.
(4)多重背包及优化（二进制，单调队列）
２２
若有n种物品，背包容量为m，物品体积、价值、最大使用次数为v,w,c，则朴素的动
规方程为：f[i]=max{f[i-v*k]+w*k} (1<=k<=c)。我们把所有可能达到的体积按照除以当前物品体积v的余数划分为0~v-1，则当余数为k(k∈[0,v-1])时又可以划分为k,k+v,k+2*v?k+j*v?（1<=j<=(m-k)div v）这几种具体的体积，由于对于余数为k时的转移只会发生在以上列举出的几个体积上，所以可以建立关于以上几个体积的单调队列，以便于快速地找到最优决策。但是这里要注意一点，由于这几个决策的体积和价值都不相同，直接没有可比性，所以我们把这些决策的体积统一到为k时比较，统一方法只需要利用体积为k+j*v这一特点，把需要插入队中的f[k+j*v]的价值减去j*w，就是当体积为k时的一个可以用于比较的“参考”价值。可以很容易想到：由于转移时，使用当前物品贡献的那一部分是二者之差，所以这与减掉j*w之前是等效的。
这样，每次求f[k+j*v]时，只需要在队列中找到一个最优的决策f[k+j’*v]，使得j-j’<=c即可，剩下的工作就只有维护单调队列了。
procedure insert(x,y:longint);
//插入到一个价值单调递减，使用次数单调递增的队列中
begin
while (l<=r)and(b[r]<=y) do dec(r); inc(r);a[r]:=x;b[r]:=y; end; begin
readln(n,m); //n为物品个数、m为背包容量 for i:=1 to n do begin
read(v,w,c);
//读入当前物品：v为物品体积、w为物品价值、c为物品可用次数 if m div v for k:=0 to v-1 do //把所有的体积按除以v的余数划分为0~v-1 begin l:=1;r:=0; //清空队列 for j:=0 to (m-k) div v do //余数为k的又分为k,v+k,2*v+k?j*v+k? begin insert(j,f[j*v+k]-j*w); //等效于把体积统一到k，价值减去j*w，这样比较优劣才有意义 while a[l] f[j*v+k]:=b[l]+j*w; //用队列头的值更新f[j*v+k] end; end; end; writeln(f[m]); end. 4. 线性DP ２３ ?线型动态规划问题，最典型的特征就是状态都在一条线上，并且位置固定，问题一般都规定只能从前往后取状态，解决的办法是根据前面的状态特征，选取最优状态作为决策进行转移。 ?设前i个点的最优值，研究前i-1个点与前i个点的最优值， ?利用第i个点决策转移 状态转移方程一般可写成: fi(k) = min{ fi-1 or j( k’) + u(i,j) or u(i,i-1) } （1） LIS最长不降子序列 {n^2} begin; readln(n); for x:=1 to n do read(a[x]); for x:=1 to n do f[x]:=1; for x:=2 to n do for y:=1 to x-1 do if a[x]>a[y] then f[x]:=max(f[x],f[y]+1); for x:=1 to n do if f[x]>ans then ans:=f[x]; writeln(ans); end. {nlogn}(二分法) var i,j,m,n,a,t:longint; f:array[1..100000] of longint; function find(l,r:longint):longint; begin while (r-l>1) do begin m:=(l+r) div 2; if f[m]=a then exit(m); if f[m] ２４
