# 50/50

1.洛谷P3399 丝绸之路 简单的线性dp

 var n,m:longint;
i,j:longint;
a,b:array[..]of longint;
f:array[..,..]of longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
for i:= to n do
for i:= to m do
for i:= to n do
begin
f[i,i]:=f[i-,i-]+a[i]*b[i];
for j:=i+ to m do
f[i,j]:=min(f[i,j-],f[i-,j-]+a[i]*b[j]);
end;
writeln(f[n,m]);
end.

2.洛谷P1435 回文字串 神奇姿势 (有点套路)

s1串中1-j 的最长公共子序列。

s[i]<>(!=)s1[j]：f[i,j]=max(f[i-1,j],f[i,j-1])

 var s,s1:ansistring;
n:longint;
f:array[..,..]of longint;
i,j:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
n:=length(s);
for i:= to n do
s1:=s[i]+s1;
for i:= to n do
for j:= to n do
if s[i]=s1[j] then f[i,j]:=f[i-,j-]+ else
f[i,j]:=max(f[i-,j],f[i,j-]);
writeln(n-f[n,n]);
end.

3.洛谷P1481 魔族密码  简单的线性dp （预处理+简单dp）

dp[i] 表示以 i 结束的串最多能有多少。

dp[i]=max(dp[j]+1)  (1≤j≤i-1)    (满足a[j] 为 a[i]的前缀)

 var
n:longint;
a:array[..]of string;
b:array[..]of longint;
i,j:longint;
dp:array[..]of longint;
ans:longint;
function ok(a,b:string):boolean;
var i:longint;
begin
for i:= to length(b) do
if a[i]<>b[i] then exit(false);
exit(true);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure qs(l,r:longint);
var i,j,m,t:longint;
s:string;
begin
i:=l;
j:=r;
m:=b[(l+r)>>];
repeat
while b[i]<m do inc(i);
while b[j]>m do dec(j);
if i<=j then
begin
t:=b[i];b[i]:=b[j];b[j]:=t;
s:=a[i];a[i]:=a[j];a[j]:=s;
inc(i);
dec(j);
end;
until i>j;
if l<j then qs(l,j);
if i<r then qs(i,r);
end;

begin
for i:= to n do
begin
b[i]:=length(a[i]);
dp[i]:=;
end;
qs(,n);
for i:= to n do
for j:= to i- do
if ok(a[i],a[j]) then
dp[i]:=max(dp[j]+,dp[i]);
for i:= to n do
ans:=max(ans,dp[i]);
writeln(ans);
end.

const base=;
HR=;
var
n:longint;
a:array[..]of string;
b,id:array[..]of longint;
hash:array[..,..]of longint;
i,j:longint;
dp:array[..]of longint;
ans:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure qs(l,r:longint);
var i,j,m,t:longint;
s:string;
begin
i:=l;
j:=r;
m:=b[(l+r)>>];
repeat
while b[i]<m do inc(i);
while b[j]>m do dec(j);
if i<=j then
begin
t:=b[i];b[i]:=b[j];b[j]:=t;
t:=id[i];id[i]:=id[j];id[j]:=t;
s:=a[i];a[i]:=a[j];a[j]:=s;
inc(i);
dec(j);
end;
until i>j;
if l<j then qs(l,j);
if i<r then qs(i,r);
end;

begin
for i:= to n do
begin
b[i]:=length(a[i]);
for j:= to length(a[i]) do
hash[i,j]:=(base*hash[i,j-]+ord(a[i][j]))mod HR;
dp[i]:=;
id[i]:=i;
end;
qs(,n);
for i:= to n do
for j:= to i- do
if hash[id[i],b[j]]=hash[id[j],b[j]] then
dp[i]:=max(dp[j]+,dp[i]);
for i:= to n do
ans:=max(ans,dp[i]);
writeln(ans);
end.

hash O(n*n)

4.洛谷P2062 分队问题 有点萌比的dp （难qaq）

QAQ还是太弱了，不是很理解。

 var n,i:longint;
f,g,a:array[..]of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure qs(l,r:longint);
var i,j,m,t:longint;
begin
i:=l;
j:=r;
m:=a[(l+r)>>];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then
begin
t:=a[i];a[i]:=a[j];a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if l<j then qs(l,j);
if i<r then qs(i,r);
end;
begin
for i:= to n do
qs(,n);
for i:= to n do
begin
if i>=a[i] then f[i]:=g[i-a[i]]+;  //注意 i-a[i] 不能小于0
g[i]:=max(f[i],g[i-]);
end;
writeln(f[n]);
end.

5.校内胡测...

f[j,k]=max(f[i,j]+1,f[j,k])    满足 xk-xj=xj-xi

 var i,j,k,x:longint;
n:longint;
f:array[..,..]of longint;
a:array[..]of longint;
ans:longint;
last:longint;
procedure qs(l,r:longint);
var i,j,m:longint;
t:longint;
begin
i:=l;
j:=r;
m:=a[(l+r)>>];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then
begin
t:=a[i];a[i]:=a[j];a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if l<j then qs(l,j);
if i<r then qs(i,r);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function find(x:longint):longint;
var l,r,m:longint;
begin
l:=last;
r:=n;
while l<r do
begin
m:=(l+r+)>>;
if a[m]<=x then l:=m else r:=m-;
end;
if a[l]=x then exit(l) else exit();
end;
begin
for i:= to n do
qs(,n);
for i:= to n- do
begin
last:=i;
for j:=i+ to n do
begin
x:=a[j]*-a[i];
k:=find(x);
if k<> then
begin
f[j,k]:=max(f[i,j]+,f[j,k]);
ans:=max(f[j,k],ans);
end;
last:=k;
end;
end;
writeln(ans);
end.

6.洛谷P2066 机器分配 简单线性dp+倒推姿势 （dp一般，倒推麻烦）

 var n,m:longint;
i,j,k:longint;
a,f:Array[..,..]of longint;
now,need:longint;
ans:array[..]of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
for i:= to n do
begin
for j:= to m do
end;
for i:= to n do
for j:= to m do
for k:= to j do
f[i,j]:=max(f[i,j],f[i-,k]+a[i,j-k]);
writeln(f[n,m]);
now:=n;
repeat
need:=;
for i:= to m do
if f[now,m]=f[now-,i]+a[now,m-i] then
if need<m-i then need:=m-i;
ans[now]:=need;
dec(m,need);
dec(now);
until now=;
for i:= to n do
writeln(i,' ',ans[i]);
end.

7.洛谷P1977 出租车拼车 简单线性dp （基础dp）

f[i,j]=f[i-1,j]  (x=0)      如果没有人上车，就不需要付 D 元

 var n,m,d,s:longint;
f:array[..,..]of longint;
t,z:array[..]of longint;
i,j,k:longint;
sum:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
for i:= to m do
begin
inc(sum,z[i]);
end;
if sum<n then
begin
writeln('impossible');
exit;
end;
for i:= to n do
f[,i]:= << ;
for i:= to m do
for j:= to n do
begin
f[i,j]:=maxlongint;
for k:= to min(z[i],j) do
if k= then f[i,j]:=f[i-,j] else
f[i,j]:=min(f[i,j],f[i-,j-k]+k*t[i]+d);
end;
writeln(f[m,n]);
end.

f[i][j] 表示 前 i 辆车载了 j 个oier的最优解。辣答案就是 f[k,n]

f[i][j]=min(f[i-1][j-x]+(n-(j-x))*(t[i]-t[i-1]))+d (1<=x<=min(z[i],j))

f[i][j]=f[i-1][j]+(n-j)*(t[i]-t[i-1]) (x=0)

 var n,m,d,s:longint;
f:array[..,..]of longint;
t,z:array[..]of longint;
i,j,k:longint;
sum:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
for i:= to m do
begin
inc(sum,z[i]);
end;
if sum<n then
begin
writeln('impossible');
exit;
end;
for i:= to n do
f[,i]:= << ;
for i:= to m do
for j:= to n do
begin
f[i,j]:=maxlongint;
for k:= to min(z[i],j) do
if k= then f[i,j]:=f[i-,j]+(n-j)*(t[i]-t[i-]) else
f[i,j]:=min(f[i,j],f[i-,j-k]+(n-j+k)*(t[i]-t[i-])+d);
end;
writeln(f[m,n]);
end.

NEW

8.洛谷P1103 书本整理 简单线性dp（基础dp）

f[i,j]=0   (j=1)

 type
node=record
w,h:longint;
end;
var i,j,k:longint;
a:array[..]of node;
n,m:longint;
f:array[..,..]of longint;
ans:longint;
procedure qs(l,r:longint);
var i,j,m:longint;
t:node;
begin
i:=l;
j:=r;
m:=a[(l+r)>>].h;
repeat
while a[i].h<m do inc(i);
while a[j].h>m do dec(j);
if i<=j then
begin
t:=a[i];a[i]:=a[j];a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if l<j then qs(l,j);
if i<r then qs(i,r);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
for i:= to n do
qs(,n);
for i:= to n do
begin
f[i,]:=;
for j:= to i do
begin
f[i,j]:=maxlongint;
for k:= to i- do
begin
if k>=j- then f[i,j]:=min(f[k,j-]+abs(a[k].w-a[i].w),f[i,j]);
end;
end;
end;
ans:=maxlongint;
for i:=n-m to n do
if f[i,n-m]<ans then ans:=f[i,n-m];
writeln(ans);
end.

9.洛谷P1279 字串距离 有趣dp（注意初始化）

②第 j 位为空格与第 i 位

③第 i 位与第 j 位

f[i,0]=f[i-1,0]+k   B串无字符，就必须用 i 个空格。

f[0,i]=f[0,i-1]+k   同理

QAQ初始化要多考虑。

 var
a,b:ansistring;
lena,lenb:longint;
i,j:longint;
k:longint;
f:array[..,..]of int64;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
lena:=length(a);
lenb:=length(b);
for i:= to lena do
f[i,]:=f[i-,]+k;
for i:= to lenb do
f[,i]:=f[,i-]+k;
for i:= to lena do
begin
for j:= to lenb do
begin
f[i,j]:=maxlongint;
f[i,j]:=min(f[i-,j]+k,f[i,j]);
f[i,j]:=min(f[i,j-]+k,f[i,j]);
f[i,j]:=min(f[i-,j-]+abs(ord(a[i])-ord(b[j])),f[i,j]);
end;
end;
writeln(f[lena,lenb]);
end.

10.洛谷P2308 添加括号 玄学区间dp+乱搞姿势 （倒推麻烦）

f[i,j]=min(f[i,k]+f[k+1,j]+sum[i,j])

 var n:longint;
i,j,k:longint;
f,sum:array[..,..]of longint;
a,ans,numl,numr:array[..]of longint;
orzn:array[..]of string;
//rp++，存有 numL[i] 个'(' 或 numR[i] 个')'
zn:longint;
ansl,ansr:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure dfs(l,r:longint);
var k,x:longint;
s1:string;
begin
if l=r then exit;
// l=r 的情况就先exit掉,这样不会统计到numL,numR中
inc(numl[l]);
inc(numr[r]);
for k:=l to r- do
if f[l,r]=f[l,k]+f[k+,r]+sum[l,r] then x:=k;
dfs(l,x);
dfs(x+,r);
inc(zn);
ans[zn]:=sum[l,r];
end;
begin
for i:= to n do
for i:= to n do
begin
f[i,i]:=;
sum[i,i]:=a[i];
for j:=i+ to n do
sum[i,j]:=sum[i,j-]+a[j];
end;
for i:=n downto  do
for j:=i+ to n do
begin
f[i,j]:=maxlongint;
for k:=i to j- do
f[i,j]:=min(f[i,k]+f[k+,j]+sum[i,j],f[i,j]);
end;
dfs(,n);
for i:= to n do
if numl[i]<> then
begin
for j:= to numl[i] do
orzn[i]:=orzn[i]+'(';
end else
begin
for j:= to numr[i] do
orzn[i]:=orzn[i]+')';
end;
for i:= to n do
if numl[i]<> then write(orzn[i],a[i],'+') else
begin
if i=n then writeln(a[i],orzn[i]) else write(a[i],orzn[i],'+');
end;
writeln(f[,n]);
for i:= to zn do
write(ans[i],' ');
writeln;
end.

11.洛谷P1140 相似基因  和第9题一样QAQ

②第 j 位为‘-’与第 i 位

③第 i 位与第 j 位

 const
c:array[''..'',''..'']of longint=((,-,-,-,-),
(-,,-,-,-),
(-,-,,-,-),
(-,-,-,,-),
(-,-,-,-,));
var n,m:longint;
a,b:string;
i,j:longint;
f:array[..,..]of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
delete(a,,);
delete(b,,);
for i:= to n do
begin
if a[i]='A' then a[i]:='' else
if a[i]='C' then a[i]:='' else
if a[i]='G' then a[i]:='' else
if a[i]='T' then a[i]:='';
f[i,]:=f[i-,]+c[a[i],''];
end;
for i:= to m do
begin
if b[i]='A' then b[i]:='' else
if b[i]='C' then b[i]:='' else
if b[i]='G' then b[i]:='' else
if b[i]='T' then b[i]:='';
f[,i]:=f[,i-]+c[b[i],''];
end;
for i:= to n do
for j:= to m do
begin
f[i,j]:=-maxlongint;
f[i,j]:=max(f[i-,j]+c['',a[i]],f[i,j]);
f[i,j]:=max(f[i,j-]+c['',b[j]],f[i,j]);
f[i,j]:=max(f[i-,j-]+c[a[i],b[j]],f[i,j]);
end;
writeln(f[n,m]);
end.

12.codevs 1184 瓷砖覆盖  状压dp入门 （入门状压）

QAQ最近既然开了dp坑，就顺便把状压一起学了吧唔...

 const HR=;
var f:array[..,..]of int64;
n,m:longint;
i,j:longint;
procedure dfs(x:longint;nows,news:int64);
// 铺到第 x 个格子。当前行状态为nows 下一行状态为news
begin
if x=m+ then  //第 i 行铺满了就进行转移了。
begin
inc(f[i+,news],f[i,nows]);
if f[i+,news]>=HR then f[i+,news]:=f[i+,news] mod HR;
//膜神犇rp++ 常数--
exit;
end;
//  shl (x-) and nows 是判断 nows 的第 x 格是否是1 如果是1则>
// 对于 x 格是1的情况不需要铺
if ( shl (x-)) and nows> then dfs(x+,nows,news) else
begin
if (( shl x) and nows=)and(x+<=m) then dfs(x+,nows,news);
// 对于 x+ 格也是0 时，可以铺横的。对下一行无影响
dfs(x+,nows,news or ( shl (x-)));
// 铺竖的，对下一行的影响就是 把 x 这个位置变成
// news or ( shl (x-)) 就是 对news 的第 x 格置1的操作
end;
end;
begin
//读入m,n 而不读入n,m是因为m过于大  <<m会爆掉
//而且2^m效率是会挂的。
f[,]:=;  //第  层什么都不铺的方案为1
for i:= to n do  //枚举铺的每一层
for j:= to ( shl m) - do //枚举 i 层的所有状态
if f[i,j]<> then dfs(,j,); //如果是可行状态就对下一层进行转移
writeln(f[n+,]);
end.

codevs1184

13.洛谷P1879 [USACO06NOV]玉米田Corn Fields  状压dp入门题

 const HR=;

var n,m:longint;
i,j,k:longint;
ans:longint;
f:array[..,..]of longint;
a:array[..,..]of longint;
function isnot(i,x:longint):boolean;
begin
exit( << (i-) and x>);
end;
function ok(c,x:longint):boolean;
var i:longint;
begin
for i:= to m do
begin
if (isnot(i,x))and(a[c,i]=) then exit(false);
if (i>)and(isnot(i,x))and(( << (i-)) and x>) then exit(false);
end;
exit(true);
end;
function check(x,y:longint):boolean;
var i:longint;
begin
for i:= to m do
if isnot(i,x)and isnot(i,y) then exit(false);
exit(true);
end;
begin
for i:= to n do
begin
for j:= to m do
end;
f[,]:=;
for i:= to n do
for j:= to ( << m)- do
if ok(i,j) then
begin
for k:= to ( << m)- do
if ok(i-,k) and check(j,k) then
begin
inc(f[i,j],f[i-,k]);
if f[i,j]>=HR then f[i,j]:=f[i,j] mod HR;
end;
if i=n then
begin
inc(ans,f[i,j]);
if ans>=HR then ans:=ans mod HR;
end;
end;
writeln(ans);
end.

14.bzoj1087(codevs2451) 互不侵犯King  状压dp

15.bzoj1879 [SDOI2009]Bill的挑战   状压dp

15题辣！=v=

16.洛谷P1336 最佳课题选择   （一般）

f[0,0]=0  不用课题，不完成论文的最优解就是 0

 var n,m:longint;
a,b:array[..]of longint;
f:array[..,..]of int64;
i,j,x:longint;
function min(a,b:int64):int64;
begin
if a<b then exit(a) else exit(b);
end;
function ksm(a,b:int64):int64;
var t,y:int64;
begin
t:=;
y:=a;
while b<> do
begin
if b and = then t:=t*y;
y:=y*y;
b:=b shr ;
end;
exit(t);
end;
begin
for i:= to m do
for i:= to n do
f[,i]:=maxlongint;
for i:= to m do
for j:= to n do
begin
f[i,j]:=maxlongint;
for x:= to j do
f[i,j]:=min(f[i,j],f[i-,j-x]+a[i]*ksm(x,b[i]));
end;
writeln(f[m,n]);
end.

luogu P1336

17.洛谷P2029 跳舞 乱写dp （一般）

f[0,0]=0

 var i,j:longint;
s,b:array[..]of longint;
f:array[..,..]of longint;
n,t,ans:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
for i:= to n do
for i:= to n do
for i:= to n do
begin
f[i,]:=f[i-,]-s[i];
for j:= to i do
if j mod t= then f[i,j]:=max(f[i-,j]-s[i],f[i-,j-]+s[i]+b[i]) else
f[i,j]:=max(f[i-,j]-s[i],f[i-,j-]+s[i]);
end;
for i:= to n do
ans:=max(ans,f[n,i]);
writeln(ans);
end.

luoguP2029

18.洛谷P2704 炮兵阵地   状压dp

f[i,j,x] 表示 前 i 行 第i行为 j 状态 第 i-1 行为 x 状态的最优解

can[i,j] 表示 i 状态和 j 状态拼起来后是否合法 若合法就 true 不合法就是 false

 var n,m:longint;
x,y,i,j:longint;
num:array[-..,..]of longint;
can:array[..,..]of boolean;
f:array[-..,..,..]of longint;
ans:longint;
a:array[..,..]of char;
function isnot(x,i:longint):boolean;
begin
exit(x and ( << (i-))>);
end;
function ok(thei,x:longint):longint;
var i,s:longint;
begin
s:=;
for i:= to m do
begin
if isnot(x,i) then inc(s);
if (a[thei,i]='H')and(isnot(x,i)) then exit(-);
if (i>=)and(isnot(x,i)and isnot(x,i-)) then exit(-);
if (i>=)and(isnot(x,i)and isnot(x,i-)) then exit(-);
end;
exit(s);
end;
function check(a,b:longint):boolean;
var i:longint;
begin
for i:= to m do
if isnot(a,i)and isnot(b,i) then exit(false);
exit(true);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
for i:= to n do
begin
for j:= to m do
end;
for i:= to n do
for j:= to ( << m)- do
num[i,j]:=ok(i,j);
for j:= to ( << m)- do
begin
num[,j]:=-;
num[-,j]:=-;
end;
for i:= to ( << m)- do
for j:= to ( << m)- do
can[i,j]:=check(i,j);
for i:= to n do
for j:= to ( << m)- do
if num[i,j]>= then
begin
for x:= to ( << m)- do
if (num[i-,x]>=)and(can[j,x]) then
begin
for y:= to ( << m)- do
if (num[i-,y]>=)and(can[j,y])and(can[x,y]) then
f[i,j,x]:=max(f[i-,x,y]+num[i,j],f[i,j,x]);
if i=n then ans:=max(f[i,j,x],ans);
end;
end;
writeln(ans);
end.

19.洛谷P2915 [USACO08NOV]奶牛混合起来Mixed Up Cows   状压dp

f[i,j or (1 << (i-1))]+=f[k,j]

 var n,m:longint;
a:array[..]of longint;
f:array[..,..]of int64;
i,j,k:longint;
ans:int64;
function ok(thei,x:longint):boolean;
var i:longint;
begin
exit(x and ( << (thei-))=);
end;
begin
for i:= to n do
for i:= to n do
f[i,( << (i-))]:=;
for j:= to ( << n)- do
for i:= to n do
if ok(i,j) then
begin
for k:= to n do
if not ok(k,j) then
if abs(a[k]-a[i])>m then inc(f[i,j or ( << (i-))],f[k,j]);
end;
for i:= to n do
inc(ans,f[i,( << n)-]);
writeln(ans);
end.

20.P1273 有线电视网  树形dp （较难）

dp[x,j]=max(dp[x,j],dp[x,j-k]+dp[now,k]-e[i].z)    now为x的儿子，这个方程就是 枚举k 表示now这个儿子的子树中选了k个子节点。

 type
node=record
y,z:longint;
next:longint;
end;
var n,m:longint;
x,z,k,ans:longint;
i,j:longint;
dp:Array[..,..]of longint;
e:array[..]of node;
tot:longint;
first,sum:array[..]of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
e[tot].next:=first[x];
e[tot].y:=y;
e[tot].z:=z;
first[x]:=tot;
inc(tot);
end;
procedure dfs(x:longint);
var i,j,k,now:longint;
begin
i:=first[x];
while i<>- do
begin
now:=e[i].y;
dfs(now);
i:=e[i].next;
inc(sum[x],sum[now]);
end;
i:=first[x];
while i<>- do
begin
now:=e[i].y;
for j:=sum[x] downto  do
for k:= to min(sum[now],j) do
dp[x,j]:=max(dp[x,j],dp[x,j-k]+dp[now,k]-e[i].z);
i:=e[i].next;
end;
end;
begin
for i:= to n do
first[i]:=-;
for i:= to n-m do
begin
for j:= to k do
begin
end;
end;
for i:= to n do
for j:= to m do
dp[i,j]:=- << ;
for i:=n-m+ to n do
begin
sum[i]:=;
end;
dfs();
for i:= to m do
if dp[,i]>= then ans:=i;
writeln(ans);
end.

21.cf910A   入门dp （最简单）

dp[j]=min(dp[i]+1,dp[j])   (s[j]="1")

 var n,d:longint;
i,j:longint;
s:string;
dp:array[..]of longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
for i:= to n do
dp[i]:= << ;
dp[]:=;
for i:= to n- do
for j:=i+ to min(i+d,n) do
if s[j]='' then dp[j]:=min(dp[i]+,dp[j]);
if dp[n]= <<  then dp[n]:=-;
writeln(dp[n]);
end.

cf910A

22.cf909C 比较灵活的dp+前缀和优化 （难）

dp[i,j]表示到第 i 行代码，这行代码用了 j 个缩进

②代码的缩进是 1

③代码的缩进是 1

④代码的缩进是 2

如果第 i 条代码是 “s” 那下一条代码可以是 ≤i 缩进的 任意缩进

这个情况下 我萌设 i+1的缩进为 j    i 的缩进为 k  则满足（0≤j≤k≤n-1） 所以 dp[i+1,j]+=dp[i,k]

dp[i+1,j]+=dp[i,k]   (s[i]="s")

 Const HR=;
var n,ans,num:int64;
i,j,k:longint;
c:array[..]of char;
dp:array[..,..]of int64;
sum:array[..]of int64;
begin
for i:= to n do
dp[,]:=;
for i:= to n do
begin
sum[]:=dp[i,];
for j:= to n- do
sum[j]:=(sum[j-]+dp[i,j])mod HR;
for j:= to n- do
begin
if c[i]='f' then
begin
if j> then dp[i+,j]:=dp[i,j-];
end else
begin
num:=sum[n-];
if j> then num:=(num+HR-sum[j-]) mod HR;
//注意因为我是前缀和，需要减，所以mod就要改成 +HR 后再mod
inc(dp[i+,j],num);
if dp[i+,j]>=HR then dp[i+,j]:=dp[i+,j] mod HR;
end;
end;
end;
writeln(sum[n-]);
end. 

cf909C

23.洛谷 P1164 小A点菜 入门背包dp （入门背包）

f[j]+=f[j-a[i]]

 var n,m:longint;
i,j:longint;
f:array[..,..]of longint;
a:array[..]of longint;
begin
for i:= to n do
f[,]:=;
for i:= to n do
for j:= to m do
begin
if j>=a[i] then f[i,j]:=f[i,j]+f[i-,j-a[i]];
f[i,j]:=f[i,j]+f[i-,j];
end;
writeln(f[n,m]);
end.

 var n,m:longint;
i,j:longint;
f:array[..]of longint;
a:array[..]of longint;
begin
for i:= to n do
f[]:=;
for i:= to n do
for j:=m downto a[i] do
if j>=a[i] then f[j]:=f[j]+f[j-a[i]];
writeln(f[m]);
end.

24.洛谷 P1064 金明的预算方案 改良背包 （套路）

①不选这个主件。

②只选这个主件。

③选这个主件外加第一个附件。

④选这个主件外加第二个附件。

⑤选这个主件外加第一个附件和第二个附件。

f[j]=max(f[j],f[j-a[i]]+a[i]*b[i]         ①和②

,f[j-a[i]-son[i,1]]+a[i]*b[i]+a[son[i,1]]*b[son[i,1]]    ③

,f[j-a[i]-son[i,2]]+a[i]*b[i]+a[son[i,2]]*b[son[i,2]]     ④

,f[j-a[i]-son[i,1]-son[i,2]]+a[i]*b[i]+a[son[i,1]]*b[son[i,1]]+a[son[i,2]]*b[son[i,2]])   ⑤

 var i,j,k:longint;
cost:int64;
f:array[..]of int64;
son:Array[..,..]of longint;
a,b,c:array[..]of longint;
n,m:longint;
function max(a,b:int64):int64;
begin
if a>b then exit(a) else exit(b);
end;
begin
for i:= to m do
begin
if c[i]> then
begin
inc(son[c[i],]);
son[c[i],son[c[i],]]:=i;
end;
end;
for i:= to m do
if c[i]= then
begin
for j:=n downto a[i] do
begin
cost:=a[i]*b[i];
f[j]:=max(f[j],f[j-a[i]]+cost);
for k:= to son[i,] do
if j-a[i]>=a[son[i,k]] then
f[j]:=max(f[j],f[j-a[son[i,k]]-a[i]]+cost+a[son[i,k]]*b[son[i,k]]);
cost:=cost+a[son[i,]]*b[son[i,]]+a[son[i,]]*b[son[i,]];
if j-a[i]>=a[son[i,]]+a[son[i,]] then
f[j]:=max(f[j],f[j-a[i]-a[son[i,]]-a[son[i,]]]+cost);
end;
end;
writeln(f[n]);
end.

P1064 金明的预算方案

25.P1049 装箱问题 入门背包dp （入门背包）

noip2001T4这么简单的咩qwq

 var
f:array[..]of boolean;
i,j:longint;
x,v,n:longint;

begin
f[]:=true;
for i:= to n do
begin
for j:=v downto x do
if f[j-x] then f[j]:=true;
end;
for i:=v downto  do
if f[i] then
begin
writeln(v-i);
exit;
end;
end.

26.cf914C 不资道什么dp...可能是数位？ （难+套路）

num[1]=0

num[i]=num[y]+1 (其中，2≤i≤n，y为 i 在二进制下1的个数)

dp[i,j,1]=dp[i-1,j,0]{在 i 位置取0使原来的s=t变为s≠t}+dp[i-1,j-1,1]{由于原来就是不同的，说明后面的既可以取1也可以取0，这里为取1的方案}+dp[i-1,j,1]{与上类似，这里是取0的方案}

dp[i,j,1]=dp[i-1,j-1,1]{由于原来就是不同的，说明后面的既可以取1也可以取0，这里为取1的方案}+dp[i-1,j,1]{与上类似，这里是取0的方案}

（注意：不加dp[i-1,j,0]的原因是如果加了就会和s相同，而如果加 dp[i-1,j-1,0]就会大于n，这不是正确的答案。）

5. 状压dp专题复习

状压dp专题复习 (有些题过于水,我直接跳了) 技巧总结 : 1.矩阵状压上一行的选择情况 $$n * 2^n$$ D [BZOJ2734][HNOI2012]集合选数 蒻得不行的我觉得这是一道比较难 ...

6. 树形dp专题总结

树形dp专题总结 大力dp的练习与晋升 原题均可以在网址上找到 技巧总结 1.换根大法 2.状态定义应只考虑考虑影响的关系 3.数据结构与dp的合理结合(T11) 4.抽直径解决求最长链的许多类问题( ...

7. 区间dp专题练习

区间dp专题练习 题意 1.Equal Sum Partitions ? 这嘛东西,$$n^2$$自己写去 $\$ $\$ 2.You Are the One 感觉自己智力被吊打 \(dp ...

8. 「动态规划」-数位dp专题

数位dp,今天学长讲的稍玄学,课下花了一会时间仔细看了一下,发现板子是挺好理解的,就在这里写一些: 数位dp主要就是搞一些在区间中,区间内的数满足题目中的条件的数的个数的一类题,题目一般都好理解,这时 ...

9. 【dp专题】NOIP真题-DP专题练习

这里学习一下DP的正确姿势. 也为了ZJOI2019去水一下做一些准备 题解就随便写写啦. 后续还是会有专题练习和综合练习的. P1005 矩阵取数游戏 给出$n \times m$矩阵每次在每一行取 ...

## 随机推荐

1. mono for android 获取手机照片或拍照并裁剪保存

axml <?xml version="1.0" encoding="utf-8"?> <LinearLayout xmlns:android ...

2. iOS开发系列--App扩展开发

概述 从iOS 8 开始Apple引入了扩展(Extension)用于增强系统应用服务和应用之间的交互.它的出现让自定义键盘.系统分享集成等这些依靠系统服务的开发变成了可能.WWDC 2016上众多更 ...

3. shell的if判断

shell的if判断 2012-03-16 14:53:05 分类: Python/Ruby   1 概要 有时候你需要指定shell脚本中的依靠命令的成功与否来实施不同过程的行为. if 结构允许 ...

4. jQuery之父：每天都写点代码

去年秋天,我的“兼职编程项目”遇到了一些问题:要不是从 Khan Academy 的项目里挪出时间来的话,我根本没办法将不理想的进度弥补上. 这些项目遇到了一些严重的问题.之前的工作我主要是在周末,有 ...

5. 正确导入svn拉取的工程

为什么要写这篇博文?主要是记录摸着石头过黄河的过程.之前在eclipse装了svn插件,拉取远程工程,在eclipse显示的工程,并不会分开显示模块工程,反而 是以总工程的姿态呈现.或许你觉得不管分模 ...

6. PHP中$_FILES的使用方法及注意事项说明$_FILES:经由 HTTP POST 文件上传而提交至脚本的变量,类似于旧数组$HTTP_POST_FILES 数组(依然有效,但反对使用)详细信息可参阅 POST方法上传$_FILES数组内容 ...

7. git出错

查询git的版本是否装对  32 位  64位

8. JDK 9.0.4安装过程

因为种种问题,怀疑是因为JDK版本不对劲,于是打算将JDK重新搞一下. 不看不知道,看了吓一跳,我的笔记本里现在起码有5.6甚至更多个JDK,JRE,并且由于年久失修,我也不知道这些东西怎么装上去的, ...

9. Django+Echarts画图实例

所有演示均基于Django2.0 阅读此篇文章你可以: 了解Django中aggregate和annotate函数的使用方法 获取一个Django+Echarts绘制柱状图的完整示例 需求说明 一张会 ...

10. Ubuntu安装完成后设置root密码

安装完ubuntu后没有默认的root密码,如果要设置root密码需要进行如下步骤: 1 sudo passwd 2 连续输入两次新密码