It seems that it's fun to open a pit ... Open one to have fun =v=...

It's just me dp Not very familiar with , Just open a pit to practice ... Practice first 50 topic ？ Small target ... It seems a little too much QAQ

Since it's a pit , I don't want what I wrote before ！

# 50/50

1. Luogu P3399 The Silk Road Simple linearity dp

Let me see the question

Because it's a pit, I don't want to talk about it , Let's see for ourselves , I'll talk about some interesting topics .

This question is actually quite simple .

set up f[i,j] To i A city uses j The minimum fatigue value required in a day .

Soon dp The equation comes out .  f[i,j]=min(f[i,j-1],f[i-1,j-1]+d[i]*c[j])   The first is to choose to rest, the second is to choose to go .

initialization f[i,i]=f[i-1,i-1]+a[i]*b[i]   A day without rest is worth walking every day

 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. Luogu P1435 Back string Magic pose ( It's a bit of a routine )

Let me see the question

I'm really cute after reading this question , I've thought about it for a long time dp, But I have no idea at all , Palindrome string ？ I'm not satisfied with posterity , How on earth dp... Then, of course, I can only brazenly and quietly go through the problem and try my best to exhaust the brain cells .

Oh ~ I see ...

The posture of this question has to be said to be very ingenious . Palindrome string , The reverse is the same ！ So you can reverse the original string .

then ？ Find the longest common subsequence . Why find the longest common subsequence , Because palindromes are the same , So the common part of the palindrome string is the palindrome string , Then I'm going to add something spicy that I don't have , The value to be added is the answer , The answer is small , I want the longest subsequence . This position get！

On the longest common subsequence , set up f[i,j] by s In a string 1-i

s1 In a string 1-j The longest common subsequence of .

such There are two situations , s[i]=s1[j] ： f[i,j]=f[i-1,j-1]+1

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.

Back string

3. Luogu P1481 Magic code   Simple linearity dp （ Preprocessing + Simple dp）

Let me see the question

This question is also relatively simple .

dp[i] Said to i How many strings can end at most .

Soon there will be dp equation

dp[i]=max(dp[j]+1)  (1≤j≤i-1)    ( Satisfy a[j] by a[i] The prefix of )

Because it's a prefix , Then the title guarantees two strings without repetition , So we should first arrange the following order according to the keyword of length , This ensures i There must have been no a[i] The prefix of because i The length after that is greater than or equal to i Of , And the length equals i It can't be a[i]( Two strings without repetition ). So the sequence guarantees dp The posterity of .

This equation is triple if it is transferred Efficiency is O(n*n*s)  n Only 2000 s Only 75 So triple de watering is OK .

Can it be double ？ Certainly. , You can preprocess each string 1-i This prefix is hash value , And then when you transfer, you can judge hash Just fine .

This efficiency is O(n*n) Cut off s When s A lot of things hash It's quite necessary .

 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.

Magic code O(n*n*s)

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)

because s It's small, so I just wrote 1hash You can go through the water ,s It is suggested to change it to 2hash even to the extent that 3hash.

4. Luogu P2062 Unit problem It's kind of cute dp （ difficult qaq）

Let me see the question

I didn't mean to see it in Luogu , I found that I'd known you before , I remember a time srm( Some interesting self test ) The topic .

And then I went and flipped , It's a discovery （ I found the original question 2333）... At that time, the problem was greedy, and it was very miserable , Positive solution dp Very short

But I still don't understand it after a long time ( Yes , I see the problem solved ).

It's about using a f[i]   Express 1 To i in Yes i The optimal solution of the problem is .

Then use one  g[i] Express f[1]..f[i-1] Maximum of .

In this way, for f[i] It can be transferred like this   f[i]=g[i-a[i]]+1   In general, I understand it as , It can be transferred by the maximum of the previous optimal solution , This ensures that the updated answer will also be an optimal solution .

as for i-a[i] I'm just choosing i This element guarantees i need a[i] individual So it has to be 1 To i-a[i] Choose between intervals , And then because of g[i] This maximum value has been saved , So just use g[i-a[i]] to update .

And then to g My update is g[i]=max(f[i],g[i-1]) This will save the maximum value .

QAQ It's still too weak , Not really understood .

 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]]+;  // Be careful  i-a[i]  Not less than 0
g[i]:=max(f[i],g[i-]);
end;
writeln(f[n]);
end.

Unit problem

5. On campus Hu test ...

The question is n (5000) individual coordinate xi（ Different from each other ）, There are two pieces , It can be initially placed here n In three coordinates . If meet i,j There are chess pieces , And in n One of the coordinates is k coordinate And meet k-j=j-i Spicy? i You can jump to k Location , How many times can I jump at most .

The question should be n^2 I wrote about efficiency n^2logn（ It looks like it is. n^2...QAQ）.

set up f[i,j] Express The first piece is  xi  Location , The second piece is xj Location end , The maximum number of steps to jump .  (xi<xj)

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

The answer is max(f[i,j])  (1≤i≤n-1, i<j≤n)

This is a n^3 Of dp There's obviously an optimization , To determine the i,j    xk You can work it out and k You can search in two . （ Sort first so that xi Orderly ）

It's obviously optimized to n^2logn

But there's another optimization , about i unchanged j increase , k It's bound to increase . So the interval of two points at a time can also be narrowed .

And then it was written in a strange way by me AC 了 =v=

 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.

On campus Hu test

6. Luogu P2066 Machine allocation Simple linear dp+ Push backwards （dp commonly , Push back the trouble ）

Let me see the question

This question is also relatively simple ...

set up f[i,j] Express front i All together, the companies used j The optimal solution of a machine . The answer is f[n,m]

Ramo equation is easy to write     f[i,j]=max(f[i-1,k]+a[i,j-k])  (0≤k≤j)

To name one k Express front i-1 A company used k platform Is the first i A company needs to have j-k platform

As for the output of the scheme , We can use the method of backward deduction from n,m Push back Because of the minimum dictionary order , So when you push backward, take the maximum dictionary order .

 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.

Luogu P2066

7. Luogu P1977  Taxi sharing   Simple linear dp （ Basics dp）

Let me see the question

This question seems to be the same as the previous one QAQ... I found two of the same questions ...

Same as the previous question   set up f[i,j] Express front i There's a car j individual oier The best solution . The answer is f[k,n]

The equation is the same QAQ   f[i,j]=min(f[i-1,j-x]+x*t[i]+d)  (1≤x≤min(z[i],j))

f[i,j]=f[i-1,j]  (x=0)       If no one gets on the bus , You don't have to pay D element

Then the initial value is the point of attention   f[0,j]=∞ (1≤j≤n)( The first 0 Every passenger in a car is of infinite value , Because I can't carry )

 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.

Luogu P1977

There seems to be something wrong with the code above ...

above dp No problem , Think about another dp

f[i][j]  Express front i There's a car j individual oier The best solution . The answer is  f[k,n]

Put it another way , For the cost , Think about the cost of those who remain

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. Luogu P1103 Book sorting Simple linear dp（ Basics dp）

Let me see the question

set up f[i,j] Express   front i This book is selected from j This book is based on i The best value at the end . The answer is min(f[i,n-k])   (n-m≤i≤n)

equation ：   f[i,j]=min(f[x,j-1])+abs(a[x].w-a[i].w)    (1≤k≤i-1)  (2≤j≤i)

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.

Luogu P1103

9. Luogu P1279 String distance Interesting dp（ Note initialization ）

Let me see the question

In this case QAQ It's kind of weird QAQ, I think about it for a while . Then I read the solution quietly .

I found that the solution is similar to what I wrote dp QAQ.

set up f[i,j] Express A In front of me i Characters ,B In front of me j The minimum distance of characters . The answer is f[lena,lenb].

equation ：  f[i,j]=min(f[i-1,j]+k,f[i,j-1]+k,f[i-1,j-1]+abs(a[i]-b[j]))

There are three types of consideration ① The first i The space and the number of j position

② The first j The space and the number of i position

③ The first i Place and number j position

And then I hung up QAQ And quietly open the problem

I didn't think about initialization .

f[i,0]=f[i-1,0]+k   B The string has no characters , It has to be used. i A space .

f[0,i]=f[0,i-1]+k   Empathy

QAQ Consider more about initialization .

 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.

Luogu P1279

10. Luogu P2308 Add brackets Metaphysical interval dp+ Fiddle with posture （ Push back the trouble ）

Let me see the question

This question is also strange QAQ.

The second question is the most basic merging of stones   set up f[i,j] Express i To j The minimum value after merging in . The answer is f[1,n]

Preprocessing an array sum[i,j] Means to merge i To j What is the value after  sum[i,j]=sum[i,j-1]+a[j]

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

The point is the first question and the third question .

For these two questions, we can ask together .

Use one dfs from [1,n] This state pushes back one at a time x  Express At present [l,r] State is to use [l,x] and [x+1,r] Transferred from .

And then for the first question , Think about it like this , Record a numL[i] Express i As l It's been recursive a few times . From the observation of the title, we can find that ,i  As l  The number of times it was recursive （ except l=r=i situations ） Namely i front ( And i Connected to a ) The left bracket number of .

Allied , Record a numR[i] Express i As r It's been recursive a few times . Or from the observation of the title ,i  As r The number of times it was recursive （ except l=r=i situations ） Namely i hinder ( And i Connected to a ) The number of right brackets .

Of course If numL[i]≠0 be numR[i]=0   Because it removes l=r=i situations .

And then in the output For each number, the front output numL[i] individual ‘(’   Back output numR[i] individual ‘)’     Then add... Between the two numbers ‘+’ Just characters .

For the second question , Because it is dfs take [1,n] State segmentation , So it's in backtracking , Direct record sum[l,r] It's hot .

And then it's happy AC 了

 var n:longint;
i,j,k:longint;
f,sum:array[..,..]of longint;
a,ans,numl,numr:array[..]of longint;
orzn:array[..]of string;
//rp++, come into being  numL[i]  individual '('  or  numR[i]  individual ')'
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  First of all exit fall , It won't count numL,numR in
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.

Luogu P2308

11. Luogu P1140 Similar gene   And the 9 Same question QAQ

Let me see the question

set up f[i,j] Express A In front of me i Characters ,B In front of me j The maximum similarity of characters . The answer is f[lena,lenb].

equation ：  f[i,j]=max(f[i-1,j]+cost('-',a[i]),f[i,j-1]+cost('-',b[j]),f[i-1,j-1]+cost(a[i],b[j]))

There are three types of consideration ① The first i Position as ‘-’ With the first j position

② The first j Position as ‘-’ With the first i position

③ The first i Place and number j position

Initialization is the same ... Basically, it's equal to the third 9 It's a string distance .

It's just a distance meter ...

 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.

Luogu P1140

12.codevs 1184 Tiles cover   Pressure dp introduction （ Portal pressure ）

Let me see the question

QAQ Since it's open recently dp pit , By the way, let's learn the shape and pressure together ...

After reading the blog for a long time, I probably know something about it QAQ

set up f[i,j] Express To the third floor i layer front i-1 The layers are all covered , And The current layer state is j Number of alternatives .

State means ： If the grid in this layer is paved , It's spicy 1 Otherwise 0. And then such a 01 String to decimal number .

about f[i,j]<>0 The situation of ( There is such a state to transfer to the next level )： It can be transferred to i+1 layer , And to make sure front i-1 The layers are already covered with such conditions . therefore front i+1-1 layer All over the place .

Spicy for the first i So it works j state (f[i,j]<>0) dfs When you move to the next level , The state of the next layer .

then  f[i+1,news]+=f[i,j] To transfer .

 const HR=;
var f:array[..,..]of int64;
n,m:longint;
i,j:longint;
procedure dfs(x:longint;nows,news:int64);
//  To the third floor  x  Lattice . The current line status is nows  The next line status is news
begin
if x=m+ then  // The first  i  When the line is full, it is transferred .
begin
inc(f[i+,news],f[i,nows]);
if f[i+,news]>=HR then f[i+,news]:=f[i+,news] mod HR;
// Membrane God rp++  constant --
exit;
end;
//  shl (x-) and nows  Is a judgment  nows  Of the  x  Is ge 1  If it is 1 be >
//  about  x  Ge Shi 1 It doesn't need to be paved
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);
//  about  x+  So is the case 0  when , It can be laid horizontally . No impact on the next line
dfs(x+,nows,news or ( shl (x-)));
//  It's vertical , The impact on the next line is   hold  x  This position becomes
// news or ( shl (x-))  Namely   Yes news  Of the  x  The lattice 1 The operation of
end;
end;
begin
// Read in m,n  Instead of reading in n,m Because m Too big   <<m It will explode
// and 2^m Efficiency will hang up .
f[,]:=;  // The first    The plan of laying nothing on the floor is 1
for i:= to n do  // Enumerate every layer of the paving
for j:= to ( shl m) - do // enumeration  i  All the states of the layer
if f[i,j]<> then dfs(,j,); // If it's feasible, move to the next layer
writeln(f[n+,]);
end.

codevs1184

about f Array You can also scroll through array optimization . I'm too lazy to write =v=

13. Luogu P1879 [USACO06NOV] Corn field Corn Fields   Pressure dp Introductory questions

Let me see the question

Well, ... This is also a relatively simple situation dp... I don't know , Actually once =v=  ( Although I took a look at the solution , But I didn't look at it )

set up f[i,j] Express The first i That's ok And The first i The status of the line is j When the number of programs . Hot? The answer is sum(f[n,j])  j yes For the first n OK, feasible state

The lemma equation should be   f[i,j]=sum(f[i-1,k])   Just enumerate one k State represents the state of the previous line , Judge whether this state is legal or not , Just hot ！=v=

For a state x , Legality is to satisfy that there are no two adjacent lattices 1 And There is no lattice for 1 But the original map is 0 . Sure O(m) Judge .

For two states x ( Current row ) and y( Last line ) , Legality is to satisfy nonexistence Any two cells in the same column are 1. equally O(m) Judge .

In this case, the theoretical efficiency is O(n*2m*2m*m)    It looks like it's stuck , But the actual time is fast , The reason should be a little pruning .

If for the current line j The state is no longer legal There's no need to enumerate k. And legal j Not much , So actually the efficiency is very fast =v=

 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.

Luogu 1879

I don't want to comment when I understand it QAQ A lazy rabbit paper

14.bzoj1087(codevs2451)  Don't invade each other King   Pressure dp

There is a solution to the problem , After all, bzoj You can use the water blog

Let me see the solution

15.bzoj1879 [SDOI2009]Bill The challenge of   Pressure dp

Estimation is bzoj I'll write a separate article on every topic .

Let me see the solution

15 Hot topic ！=v=

also 35 topic QAQ It's a long time ...

16. Luogu P1336 The best project selection    （ commonly ）

Let me see the question

In this case , It won't be hard ...

set up  f[i,j] Before use i In this project, we have written j The optimal solution of this paper The answer is f [m,n]

Initialize to f [0,i]=∞ (1≤i≤n)   If you want to finish a thesis without a topic, it's infinity

f[0,0]=0   No problem , If you don't finish the paper, the best solution is 0

equation  f[i,j]=min(f[i-1,j-x]+a[i]*xb[i]) ( enumeration x Express The first i This is a project to write x piece )

Power. I'm going to use a fast power ... Violence should also be possible

Pay attention to the long long

 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. Luogu P2029 dance Scribble dp （ commonly ）

Let me see the question

set up f[i,j] Express To the first i individual It's on the front j individual The best solution The answer is max(f[n,i]) (1≤i≤n)

equation f[i,j]=max(f[i-1,j]-s[i],f[i-1,j-1]+s[i]+b[i])  (j mod t=0 The situation of , You can choose not to step on , Namely -s[i] And step on +s[i]+b[i])

Again f[i,j]=max(f[i-,j]-s[i],f[i-1,j-1]+s[i])    (j mod t≠0 The situation of balalala)

Initialize to  f[i,0]=f[i-1,0]-s[i]   If you don't step on any of them, you'll have to buckle them off

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. Luogu P2704 Artillery position   Pressure dp

Let me see the question

This question is very similar to 14 topic , It's just a little bit more , It's just a change of direction and terrain

Because it's about two lines , So change the equation to this

f[i,j,x] Express front i That's ok The first i Behavior j state The first i-1 Behavior x The optimal solution of the State

Then enumerate one y Express The first i-2 The state of the line , And then the violent sentence x,y,j Is it legal

If it's legal, transfer   f[i,j,x]=max(f[i,x,y]+j In state 1 Number )

obviously O（n*2m*2m*2m） Yes. T Don't want to

Think about optimization ? Of course, the idea of pruning pretreatment .

Preprocessing num[i,j] Express The first i Behavior j Whether the status is legal , If it's legal, it's j In state 1 The number of , If it's not legal , for -1

This cuts out a lot of enumeration ranges , But still T ( Lazy rabbit paper is too lazy to write optimization, so it's finished T I had to change it later )

Another optimization is To judge Is any two lines legal , This will also waste a lot of time , So pretreatment

can[i,j] Express i State and j Whether the states are legal or not If it's legal true Illegal is false

In this way, the repeated judgment time is reduced , And then it's happy AC spicy

 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.

Luogu P2704 Artillery position

19. Luogu P2915 [USACO08NOV] The cows mix Mixed Up Cows   Pressure dp

Let me see the question

Um. ... set up f[i,j] Express Status as j when The last cow is i Number of alternatives Hot? The answer is sum(f[i,1 << n-1]) (1≤i≤n)

So the equation is

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

In that case, you'll find i and k The order of priority is different , So we need to change the order of enumeration Let's enumerate j Enumerate again i,k

Um. ... It's simpler

 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.

Luogu P2915

20.P1273 Cable network   Tree form dp （ More difficult ）

Let me see the question

Um. ... I read the explanation again QAQ

set up dp[i,j] Express With i For the subtree of the root j The maximum value left after two leaf nodes .

Hot? The answer is max(i) (1≤i≤n And dp[1,i]≥0)

dp[x,j]=max(dp[x,j],dp[x,j-k]+dp[now,k]-e[i].z)    now by x Son , This equation is enumeration k Express now This son's son has chosen k Child node .

Because each leaf node can only be selected once , and 01 Backpacks are similar , therefore j To enumerate backwards .

initial value All the leaf nodes x Of dp[x,1] Money for users .

This is a n^3 Of dp, Meeting TLE (50 branch )   Think about optimization .

about x node , actually j You don't need to enumerate to m So big , Just enumerate to sum[x] （sum[x] Express With x Is the number of leaf nodes in the subtree of the root ）

This optimizes a lot of invalid enumerations , And then 100 spicy .

 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.

Luogu P1273

Miserable QAQ It's been more than a month , It's not half of it QAQ

because noip, I was going to noip I filled it out before , result dp Some of my good questions are not very easy to find （ The main reason is that I can't QAQ In addition, there is less time for the third year old rabbit ）

So pinch , I guess this pit will be empty for a while , Let's move on noip, And then if there's a brush, add a little bit in , So it's no longer limited to just brushing dp Title .

Ah ~ I've come back ！ Every time I blog, I see this top , A conscience that doesn't exist hurts qwq It's been a long time ... I still have to come back to make it up , Otherwise, the strength of the old rabbit is too good ...

Well, ... But this pit is really hard to fill qwq... So the estimate is very simple dp Put it in, too ... Just a few ... Because I've been making up for cf So the problem will enlarge the part cf Of ...cf Of dp There are not many problems ...

So the road to fill the pit is very long qwq  ( Suddenly I found that there was a dividing line ... I used to split lines manually ... It seems silly ..._(:з」∠)_)

Change the format of the pit ... This kind of thing seems very strange , Just go straight to the topic qwq Stupid rabbit paper ...

21.cf910A    introduction dp （ The most simple ）

It's OK to update the accessible places directly

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

The initial value is dp[1]=0   dp[i]=∞  (2≤i≤n)

 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 More flexible dp+ Prefixes and optimizations （ difficult ）

I don't know how to write this question at all dp... Finally, let's see the solution ... I understand , I have a general idea ...

dp[i,j] To i Line code , This line of code uses j Indents

You can find j At most n-1

initial ： dp[1,0]=1;

The first line of code must be indented to 0 Of The plan is 1

Indent means ： Pictured above    ① The indentation of the code is 0

② The indentation of the code is 1

③ The indentation of the code is 1

④ The indentation of the code is 2

The answer is sum(dp[n,i])  (0≤i≤ n-1)

Consider shifting     If the first i The code is “f”  Then the next code must be indented therefore    dp[i+1,j]=dp[i,j-1]

If the first i The code is “s” The next code could be ≤i Indented Any indent

In this case I love i+1 The indent of is j    i The indent of is k  Then meet （0≤j≤k≤n-1） therefore  dp[i+1,j]+=dp[i,k]

Put it in order ：  dp[i+1,j]=dp[i,j-1]   (s[i]="f")

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

Enumeration when transferring i and j

about k (k≥j)  If enumerating Will be O(N3)  Will timeout .

Find out dp[i,k] It can be prefixed and preprocessed （ Of course, suffixes and can also , And it's more convenient , But when I wrote it, I wrote the prefix and ah ah qwq, I'm lazy to change the code ）

So it's optimized to  O(N2) So it's unpleasant AC 了

Wow, I cried QAQ dp... good ... So hard! QAQ

 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;
// Notice because I'm prefix and , Need to be reduced , therefore mod It's going to be changed to  +HR  Later 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. Luogu  P1164 Small A May I take your order?   Entry backpack dp （ Entry backpack ）

set up f[i,j] Before presentation i A cauliflower j The number of schemes of the

initial value f[0,0]=1

For each dish you can choose or not

therefore f[i,j]=f[i-1,j-a[i]]+f[i-1,j] ( The first option , The latter is the alternative )

This is already possible AC, Consider spatial optimization , because The equations are just and i-1 Relevant , So consider scrolling arrays , Knapsack optimization .

be set up f[j]  It means flowers j The number of schemes of the

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

Note that 01 So j It's upside down

 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.

Small A May I take your order? A two-dimensional

 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.

Small A May I take your order? A one-dimensional

24. Luogu  P1064 Jin Ming's budget   Improved backpack （ tricks ）

This dp... Add a condition qwq... So I started to be cute ... Quietly Mimi took a look at the solution, and it will be solved in an instant ...

Because the most accessories are 2 individual , So preprocess the attachment of each main component first ... son[i,1] Express i The first attachment of son[i,2] Express i The second attachment of

Then divide 5 class dp Main parts

① Don't choose this main piece .

② Select only this main component .

③ Select the main component and the first accessory .

④ Select the main component and the second accessory .

⑤ Select the main component plus the first attachment and the second attachment .

And then separately dp Just a moment ...

The equation is very long qwq... And ordinary backpacks f It means the same thing

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

,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 Jin Ming's budget

I'm so lazy ... Just a little bit more difficult to put in , Otherwise, the pit will not be filled QAQ...

25.P1049 Packing problem   Entry backpack dp （ Entry backpack ）

noip2001T4 So simple baa qwq

There are many ways to solve this problem , I'm thinking about setting up f[j] Before presentation i I'll spell out j Is it feasible , If it is feasible, it is true No action false

The answer is to enumerate backwards and find one f[j]=true  The answer for v-j

If f[j-a[i]]=true be f[ j ]=f[j-a[i]]

 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.

Packing problem

It can be similar The first 23 Do the same thing , If the last f[j]>0 Equivalent to f[j]=true 了 , however bool Save space ... So I played bool

You can also think of value as volume to make a 01 knapsack ...

Many ways , There are a lot of ways to do it, so just pull it into the pit ...

26.cf914C  I don't know what dp... It could be digital ？ （ difficult + tricks ）

In this case qwq... I haven't thought about it for a long time , Quietly turned over the official solution , Do not understand , Then Baidu , Do not understand ... The only way is dp... I saw some ideas , And then I went back to thinking ...

I'm going to talk about n Change it to s.

because s Very big , Yes 21000, But think about , Find out s Just one operation , Can become smaller than 1000, because s In binary, at most 1000 position , Both are assumed 1, After operation, it becomes 1000.

For convenience , Can not be used directly 1000, I love n=length(s) namely s The number of bits in binary .

And for 1~1000  The number in , I love how many steps it takes to make a direct violent sentence into 1 Of .

Here I use something like dp A recurrence of .

set up num[i]  Express i This number becomes 1 The number of times it takes .

num[1]=0

num[i]=num[y]+1 ( among ,2≤i≤n,y by i In binary 1 The number of )

This one uses O(n log n) It can be dealt with .

At this time, I'm thinking backwards , Turn the problem into For a number x, How many y Satisfy y In binary 1 Yes x Geqi y≤n.

And for the original question , The answer is Satisfy num[x]=k-1 Of x What can be found y The sum of the number of .

well , Next is the real dp, solve Find out how many y Of dp.

set up dp[i,j,0] Express 1~i Middle selection j individual 1, And t[x]=s[x](1≤x≤i, among t It's a choice y Binary system , Such as s=“110”, that dp[3,3,0]=0{ What can be constructed t=“111”, Unable to satisfy with s identical },dp[3,2,0]=1{ What can be constructed t=“110” t=“101” t=“011”, Satisfy s=t There are 1 individual , by t=“110”})

initial value dp[0,0,0]=1.

set up  dp[i,j,1] Express 1~i Middle selection j individual 1, And there are x send t[x]≠s[x]{ say concretely ,t[x]=“0” s[x]=“1”} (1≤x≤i, among t It's a choice y Binary system , Similar to the above ,dp[3,3,1]=1,dp[3,2,1]=2)

initial value dp[i,0,1]=1.

Transfer ：

about s[i]=“1” when ：dp[i,j,0]=dp[i-1,j-1,0] { We need to make sure that we are in touch with each other s[i] Take the same , That is to take 1}

dp[i,j,1]=dp[i-1,j,0]{ stay i Location 0 Make the original s=t Turn into s≠t}+dp[i-1,j-1,1]{ Because it's different , Explain that the following can take 1 Can also take 0, Here is to take 1 The plan }+dp[i-1,j,1]{ Similar to above , This is to take 0 The plan }

about s[i]=“0”  when ：dp[i,j,0]=dp[i-1,j,0] { We need to make sure that we are in touch with each other s[i] Take the same , That is to take 0}

dp[i,j,1]=dp[i-1,j-1,1]{ Because it's different , Explain that the following can take 1 Can also take 0, Here is to take 1 The plan }+dp[i-1,j,1]{ Similar to above , This is to take 0 The plan }

（ Be careful ： No addition dp[i-1,j,0] The reason is that if it is added, it will be combined with s identical , And if you add dp[i-1,j-1,0] Will be greater than n, This is not the right answer .）

For one x The answer is dp[n,x,1]{y Don't s Same and less than s}+dp[n,x,0]{y and s identical } I'm looking for y Number of bits is n, take x individual 1 Composed of y The number of .

that ans+=dp[n,x,1]+dp[n,x,0] (1≤x≤n, And meet num[x]=k-1)

This will still wa Of .... Because there are pits , When k=0 when , The answer for 1 Special judgment is required .

This will still wa Of .... Because there's a hole , When k=1 yes , The answer needs to be reduced 1, Because the original answer will form a y=1, and 1 yes 0 It can be done in one step , but num[1]=0=k-1 It will be counted .

This will still wa Of .... Then I can't help it , Because there are no pits ~~$$≧▽≦)/~ La la la  const HR=; var s:ansistring; i,j:longint; n,k,x,y,ans:longint; dp:array[..,..,..]of longint; num:array[..]of longint; begin readln(s); n:=length(s); read(k); if k= then begin writeln(); exit; end; for i:= to n do begin x:=i; y:=; while x> do begin inc(y,x mod ); x:=x>>; end; num[i]:=num[y]+; end; dp[,,]:=; for i:= to n do begin dp[i,,]:=; for j:= to i do begin if s[i]='' then begin dp[i,j,]:=dp[i-,j-,]; dp[i,j,]:=dp[i-,j,]+dp[i-,j-,]+dp[i-,j,]; end else begin dp[i,j,]:=dp[i-,j,]; dp[i,j,]:=dp[i-,j,]+dp[i-,j-,]; end; if dp[i,j,]>=HR then dp[i,j,]:=dp[i,j,] mod HR; if dp[i,j,]>=HR then dp[i,j,]:=dp[i,j,] mod HR; end; end; for i:= to n do if num[i]=k- then begin inc(ans,(dp[n,i,]+dp[n,i,])); if ans>=HR then ans:=ans mod HR; end; if k= then dec(ans); writeln(ans); end. cf914C QAQ Current cf Of c The questions are very difficult ... I've been working on it ... 27.cf 894C Pressure dp （ difficult ） this cf It's more and more difficult qwq... The old rabbit can't hold on QAQ Wow, I cried ,div2C How come it's compressed QAQ According to the past , Can be launched , I see the problem solved ... But this time the official answer is really Mengbi , It's completely incomprehensible , Get the general information , It's similar to compression dp+ There are few prime numbers . And then I have to think for myself qwq, Anyway, I can do some shape pressing ... about 1~70 The number prime factorization in . set up dp[i,j] Express front i The prime number state is j Number of alternatives , state j Express Prime numbers , It's an even number. It's just 0, It's odd, it's just 1. initialization dp[0,0]=1 dp[i+1,j]+=dp[i,j] No a[i] dp[i+1,j xor c[a[i]]]+=dp[i,j] take a[i] xor Just enough , Two 1 or 0 Then for 0 One 0 One 1 Then for 1 Operations like this . In this way, the state can be changed accordingly . c[i] Express i After the prime factor decomposition, the corresponding state A prime number is an even number 0, It's odd, it's just 1. answer dp[n,0]-1 Subtract an empty sequence . That is to say, if we don't take any . This efficiency O(n*219) Because prime numbers have 19 individual . Preprocessing c[i] as long as O(70 log2 70 ) Because time and space will hang up , Optimize the space first , Just scroll through the array ... Of course it will TLE( The first 13 individual test) spicy ... Because rabbit players can't think of any other way to write it ... So we're doing optimization , The general optimization is to calculate 1-i Can spell out the state of j Not the whole state j. This is still TLE(13)... Think about it again , Put the same numbers together , such 1-i There will be fewer states that can be spelled out , Because the same number is xor 2 Next time, it's on the side 0 了 ... So the state doesn't increase ... So successful TLE(14) 了 ... At this time, rabbit realized that optimization does not exist ... Consider typing your watch Think hard and find a way to write QAQ. Let's assume that all numbers are not repeated at first , If you add a repeating number , In fact, it is to make this repeated number in the same way dp... that , Is there any rule . So I started to look for the rules . Let's assume that all numbers are not repeated at first , After adding a repeating number , The answer will be based on the original *2+1. After typing multiple tables , It turns out that's true QAQ So force the law , First dp It's a number that doesn't repeat efficiency O(70*219) And then in For repeated numbers , Every one more is *2+1  const HR=; var i,j,k:longint; v:array[..]of boolean; can:array[..]of longint; c:array[..]of int64; a,have:array[..]of longint; num,n,x,z,new:longint; bool:longint; dp:array[..,..]of longint; begin for i:= to do if not v[i] then begin inc(num); for j:= to div i do begin v[j*i]:=true; x:=j*i; z:=; while x mod i= do begin x:=x div i; inc(z); end; if (z mod =) then c[j*i]:=c[j*i] xor ( << (num-)); end; end; for i:= to do v[i]:=false; z:=; can[z]:=; v[]:=true; read(n); for i:= to n do begin read(a[i]); inc(have[a[i]]); if not v[c[a[i]]] then begin inc(z); can[z]:=c[a[i]]; v[c[a[i]]]:=true; end; end; dp[,]:=; bool:=; for i:= to do for k:= to have[i] do begin new:=z; for j:= to new do if dp[bool,can[j]]<> then begin inc(dp[-bool,can[j]],dp[bool,can[j]]); if dp[-bool,can[j]]>=HR then dp[-bool,can[j]]:=dp[-bool,can[j]] mod HR; inc(dp[-bool,can[j] xor c[i]],dp[bool,can[j]]); if dp[-bool,can[j] xor c[i]]>=HR then dp[-bool,can[j] xor c[i]]:=dp[-bool,can[j] xor c[i]] mod HR; dp[bool,can[j]]:=; if not v[can[j] xor c[i]] then begin inc(z); can[z]:=can[j] xor c[i]; v[can[j] xor c[i]]:=true; end; end; bool:=-bool; end; writeln(dp[bool,]-); end. cf894C TLE（14） Optimization can be learned  const HR=; var i,j,k:longint; v:array[..]of boolean; can:array[..]of longint; c:array[..]of int64; a,have:array[..]of longint; num,n,x,z,new,ans:longint; bool:longint; 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 do if not v[i] then begin inc(num); for j:= to div i do begin v[j*i]:=true; x:=j*i; z:=; while x mod i= do begin x:=x div i; inc(z); end; if (z mod =) then c[j*i]:=c[j*i] xor ( << (num-)); end; end; for i:= to do v[i]:=false; z:=; can[z]:=; v[]:=true; read(n); for i:= to n do begin read(a[i]); inc(have[a[i]]); if not v[c[a[i]]] then begin inc(z); can[z]:=c[a[i]]; v[c[a[i]]]:=true; end; end; dp[,]:=; bool:=; for i:= to do for k:= to min(have[i],) do begin new:=z; for j:= to new do if dp[bool,can[j]]<> then begin inc(dp[-bool,can[j]],dp[bool,can[j]]); if dp[-bool,can[j]]>=HR then dp[-bool,can[j]]:=dp[-bool,can[j]] mod HR; inc(dp[-bool,can[j] xor c[i]],dp[bool,can[j]]); if dp[-bool,can[j] xor c[i]]>=HR then dp[-bool,can[j] xor c[i]]:=dp[-bool,can[j] xor c[i]] mod HR; dp[bool,can[j]]:=; if not v[can[j] xor c[i]] then begin inc(z); can[z]:=can[j] xor c[i]; v[can[j] xor c[i]]:=true; end; end; bool:=-bool; end; ans:=dp[bool,]-; for i:= to do for k:= to have[i]- do begin ans:=ans*+; if ans>=HR then ans:=ans mod HR; end; writeln(ans); end. cf894C AC I didn't expect my code to run surprisingly fast , Well, it's not that fast , But at least FPC The fastest spicy food in the world ~\(≧▽≦)/~ La la la （ It's just that FPC Few players QAQ） 28. Luogu P1091 （ tricks ） This is a question of thinking , Read the explanation of the question QAQ In fact, we are looking for the length of the longest ascending subsequence , Find the length of the longest ascending subsequence inversely . dp[i,0] It means positive dp[i,1] It's upside down , Specifically dp I won't talk about it , There was talk of .（ As if qwq） Then enumeration i send max=dp[i,1]+dp[i,0]-1 The biggest is good Subtract a repeat itself . Then the answer is n-max  var n:longint; i,j:longint; dp:array[..,..]of longint; a:array[..]of longint; mx:longint; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; begin read(n); for i:= to n do begin read(a[i]); dp[i,]:=; dp[i,]:=; end; for i:= to n do for j:= to i do if a[j]<a[i] then dp[i,]:=max(dp[j,]+,dp[i,]); for i:=n downto do for j:=i to n do if a[j]<a[i] then dp[i,]:=max(dp[j,]+,dp[i,]); for i:= to n do if dp[i,]+dp[i,]->mx then mx:=dp[i,]+dp[i,]-; writeln(n-mx); end. luoguP1091 29.cf919D Topology +dp （ Simple dp+ Topological routines ） It can be found that a long road is better than a short one , So in fact, the road is bound to be an entry point for 0 The running out degree of the point is 0 The point of . In the game, choose direct spfa run 26 The second longest road . Then I didn't expect that the self ring was the ring during the game , And then all the time wa4, By zn Teach people to be rabbits . wa4 I found out some mistakes at random , Then change the ring to a topology instead of spfa. In the morning 1 It's a success after the match is over tle（33test） 了 , And then it turns out it might be stuck spfa 了 , After all spfa Metaphysical efficiency . Get up at noon in the morning and run around when you plan to change the topology dp Just fine , It is not necessary to spfa. And then it passed ...（ It's fast qwq） set up dp[i,c] Express From a certain angle to 0 From the point of departure to the point of arrival i This point passes through a point where c What is the maximum value of this character . dp[i,s[i]]=1 (i For entering, for entering 0 The point of ) Then update the topology dp dp[y,c]=max(dp[y,c],dp[x,c]+cost) ( if s[y]=c be cost by 1 Otherwise 0) The answer is max(dp[i,c]) (1≤i≤n,‘a’≤c≤‘z’) In fact, it's not hard to qwq, I think too much during the game ...  type node=record y,next:longint; end; var i:longint; n,m,tot:longint; c:char; v:array[..]of boolean; first,goin:array[..]of longint; dp:array[..,'a'..'z']of longint; e:array[..]of node; q:array[..]of longint; x,y:longint; ans:longint; s:ansistring; procedure adde(x,y:longint); begin e[tot].next:=first[x]; e[tot].y:=y; first[x]:=tot; inc(tot); end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure tupo; var head,tail:longint; i,now,y,cost:longint; c:char; begin head:=; tail:=; for i:= to n do if goin[i]= then begin inc(tail); q[tail]:=i; dp[i,s[i]]:=; end; while head<=tail do begin now:=q[head]; i:=first[now]; while i<>- do begin y:=e[i].y; for c:='a' to 'z' do begin if c=s[y] then cost:= else cost:=; dp[y,c]:=max(dp[y,c],dp[now,c]+cost); end; dec(goin[y]); if goin[y]= then begin inc(tail); q[tail]:=y; end; i:=e[i].next; end; inc(head); end; if tail<>n then begin writeln(-); halt; end; end; begin readln(n,m); readln(s); for i:= to n do first[i]:=-; for i:= to m do begin read(x,y); if x<>y then begin adde(x,y); inc(goin[y]); end else begin writeln(-); exit; end; end; tupo; for i:= to n do for c:='a' to 'z' do if dp[i,c]>ans then ans:=dp[i,c]; writeln(ans); end. cf919D 30. Luogu P1282 Simple linear dp （ commonly , It's a bit of a routine ） set up dp[i,j] Before presentation i The difference between two dominoes is j The minimum cost of time . j Can be negative ,c++ Just move it ... dp[i,j+a-b]=min(dp[i-1,j]) dp[i,j+b-a]=min(dp[i-1,j]+1) It's a bit too much to think about space consumption , Just scroll through the array and optimize it , You can live without optimization ~\(≧▽≦)/~ La la la  var n:longint; i,j:longint; a,b:longint; dp:array[..,-..]of longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; begin read(n); for i:=- to do dp[,i]:=maxlongint; dp[,]:=; for i:= to n do begin read(a,b); for j:=- to do dp[i,j]:=maxlongint; for j:=- to do if dp[i-,j]<>maxlongint then begin dp[i,j+a-b]:=min(dp[i,j+a-b],dp[i-,j]); dp[i,j+b-a]:=min(dp[i,j+b-a],dp[i-,j]+); end; end; for i:= to do if min(dp[n,i],dp[n,-i])<>maxlongint then begin writeln(min(dp[n,i],dp[n,-i])); exit; end; end. luoguP1282 No scrolling array  var n:longint; i,j:longint; a,b:longint; dp:array[..,-..]of longint; bool:longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; begin read(n); for i:=- to do begin dp[,i]:=maxlongint; dp[,i]:=maxlongint; end; dp[,]:=; bool:=; for i:= to n do begin read(a,b); for j:=- to do if dp[bool,j]<>maxlongint then begin dp[-bool,j+a-b]:=min(dp[-bool,j+a-b],dp[bool,j]); dp[-bool,j+b-a]:=min(dp[-bool,j+b-a],dp[bool,j]+); dp[bool,j]:=maxlongint; end; bool:=-bool; end; for i:= to do if min(dp[bool,i],dp[bool,-i])<>maxlongint then begin writeln(min(dp[bool,i],dp[bool,-i])); exit; end; end. luoguP1282 Scrolling array 31. Luogu P1020 Deformation of the longest ascending sequence （ Data structure optimization dp+ tricks ） First, ask for the longest Don't go up Sequence , because n Larger can use tree arrays or other strange dp+ Dichotomous Since tree arrays seem to be rarely written , And I only know about tree arrays , So I wrote this . Because the original dp requirement 1~i-1 Greater than a[i] It's worth it dp[j] Maximum The tree array can be used to find the maximum value of suffix sum . Generally speaking, I'm looking for l , r The maximum value of is realized with a number like array logn2 The efficiency of . But there's no need for that , Because the query will only query the maximum value of suffix sum , That is, only l r It's fixed to the maximum . So the modification can directly take max The same is true for queries max. Be careful ： If you need to inquire l~r And single point modification operation , You can't use this method , The specific writing method is Baidu . I suggest line segment tree implementation . The second question is a routine , It's actually the longest ascending sequence . This guarantees that all numbers can be covered . It's equivalent to finding the longest one backwards falling Sequence , So just a tree array upside down . Notice that it's different from the first question , It's down here, not up here .  var n,m:longint; dp,tree,a:array[..]of longint; i:longint; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function low(x:longint):longint; begin exit(x and -x); end; procedure adde(x,d:longint); begin while x> do begin tree[x]:=max(tree[x],d); dec(x,low(x)); end; end; function getmax(x:longint):longint; var s:longint; begin s:=; if x= then exit(s); while x<=m do begin s:=max(tree[x],s); inc(x,low(x)); end; exit(s); end; begin while not eoln do begin inc(n); read(a[n]); m:=max(m,a[n]); end; for i:= to n do begin dp[i]:=getmax(a[i])+; adde(a[i],dp[i]); end; writeln(getmax()); for i:= to m do begin tree[i]:=; dp[i]:=; end; for i:=n downto do begin dp[i]:=getmax(a[i]+)+; adde(a[i],dp[i]); end; writeln(getmax()); end. luoguP1020 By Some big guy Hurry up QAQ, The third year of junior high school begins QAQ Make it up when you have time ... Strive for summer vacation c++ Fill in before ... 32. Luogu P1508 introduction dp （ introduction ） Direct pyramid deformation ... No more details ... Ow  var m,n:longint; i,j:longint; dp,a:array[..,..]of int64; ans:int64; function max(a,b:int64):int64; begin if a>b then exit(a) else exit(b); end; begin read(m,n); for i:= to m do begin dp[i,]:=-maxlongint; dp[i,n+]:=-maxlongint; for j:= to n do begin read(a[i,j]); dp[i,j]:=-maxlongint; if i=m then dp[i+,j]:=-maxlongint; end; readln; end; dp[m+,]:=-maxlongint; dp[m+,n+]:=-maxlongint; dp[m+,(n+) div ]:=; for i:=m downto do for j:= to n do begin dp[i,j]:=max(dp[i,j],dp[i+,j]+a[i,j]); dp[i,j]:=max(dp[i,j],dp[i+,j-]+a[i,j]); dp[i,j]:=max(dp[i,j],dp[i+,j+]+a[i,j]); end; ans:=-maxlongint; for i:= to n do ans:=max(dp[,i],ans); writeln(ans); end. luoguP1508 33.cf 31E Just a simple decision dp （ introduction ） set up dp[i,j] Before presentation i Characters Yes j Yes A List of The maximum and that b The string has i-j individual Considering that the sum can be divided into the sum of every bit And then enumerate i then dp Want this s[i] Go to A String or B Just string set up num Express s[i] How much is this character converted into a number ten[i] Express 10 Of i Power （10i dp[i+1,j+1]=max(dp[i,j]+num*ten[n-j-1]); dp[i+1,j]=max(dp[i,j]+num*ten[n-i+j-1]); These strange subscripts can be pushed by drawing a picture Ask for the end dp It's better to choose the best one for each step It should be OK to turn it upside down , But I hung up ... Lazy tune QAQ  var n:longint; s:array[..]of char; ans:array[..,..]of string; i,j:longint; ten:array[..]of int64; num:int64; dp:array[..,..]of int64; function max(a,b:int64):int64; begin if a>b then exit(a) else exit(b); end; function min(a,b:int64):int64; begin if a<b then exit(a) else exit(b); end; begin readln(n); ten[]:=; for i:= to *n do begin read(s[i]); if i<=n then ten[i]:=ten[i-]*; end; readln; for i:= to *n- do begin num:=ord(s[i+])-; for j:=max(,i-n) to min(n,i) do begin if (j<n)and(dp[i+,j+]<dp[i,j]+num*ten[n-j-]) then dp[i+,j+]:=dp[i,j]+num*ten[n-j-]; if (i-j<n)and(dp[i+,j]<dp[i,j]+num*ten[n-i+j-]) then dp[i+,j]:=dp[i,j]+num*ten[n-i+j-]; end; end; for i:= to *n- do begin num:=ord(s[i+])-; for j:=max(,i-n) to min(n,i) do begin if (j<n)and(dp[i+,j+]=dp[i,j]+num*ten[n-j-]) then ans[i+,j+]:=ans[i,j]+'H'; if (i-j<n)and(dp[i+,j]=dp[i,j]+num*ten[n-i+j-]) then ans[i+,j]:=ans[i,j]+'M'; end; end; writeln(ans[*n,n]); end. cf31E 34. Luogu P1387 It's a little bit unconventional dp （ More difficult ） n It's relatively small. You can write water however dp Seems to be the best I didn't think of it at first. I just wrote n3 And ... After reading the question, I understand Maybe I write less questions of this type set up f[i,j] Said to i ,j This point is the side length of the largest square that the lower right corner can form Just look at a picture So is f[i,j]=min(f[i,j-1],f[i-1,j],f[i-1,j-1])+1  var n,m:longint; i,j:longint; ans:longint; f,a:array[..,..]of longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; begin read(n,m); for i:= to n do begin for j:= to m do read(a[i,j]); readln; end; for i:= to n do begin for j:= to m do if a[i,j]= then begin f[i,j]:=min(min(f[i-,j],f[i,j-]),f[i-,j-])+; if f[i,j]>ans then ans:=f[i,j]; end end; writeln(ans); end. luoguP1387 35. Luogu P1855 A two-dimensional 01 knapsack Naked dp[i,j]=max(dp[i-time[k],j-money[k]]+1)  var n,m,t:longint; i,j,k:longint; time,mo:array[..]of longint; dp:array[..,..]of longint; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; begin read(n,m,t); for i:= to n do read(time[i],mo[i]); for k:= to n do begin for i:=m downto mo[k] do for j:=t downto time[k] do dp[i,j]:=max(dp[i-mo[k],j-time[k]]+,dp[i,j]); end; writeln(dp[m,t]); end. luoguP1855 36. Luogu P1541 Multidimensional dp set up dp[i,j,k,p] It means to use i Zhang 1 Of j Zhang 2 Of k Zhang 3 Of p Zhang 4 Of set up x=i+j*2+k*3+p*4+1 dp[0,0,0,0]=a[1] dp[i,j,k,p]=max(dp[i-1,j,k,p],dp[i,j-1,k,p],dp[i,j,k-1,p],dp[i,j,k,p-1])+a[x] It's not hard to ... It's just that multidimensional writing is a little boring , So the data range is wrong ...QAQ  var n,m:longint; i,j,k,p:longint; cost:longint; x:longint; num:array[..]of integer; dp:array[-..,-..,-..,-..]of longint; a:Array[..]of longint; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; begin read(n,m); for i:= to n do read(a[i]); for i:= to m do begin read(x); inc(num[x]); end; dp[,,,]:=a[]; for i:= to num[] do for j:= to num[] do for k:= to num[] do for p:= to num[] do begin x:=i+j*+k*+p*+; cost:=max(dp[i-,j,k,p],dp[i,j-,k,p]); cost:=max(dp[i,j,k-,p],cost); cost:=max(dp[i,j,k,p-],cost); dp[i,j,k,p]:=max(dp[i,j,k,p],cost+a[x]); end; writeln(dp[num[],num[],num[],num[]]); end. luoguP1541 37. Luogu P1137 Topologically simple dp （ Topological routines +dp） set up dp[i] Express With i Is the maximum value that the destination can pass through . dp[y]=max(dp[x]+1) Think about this dp Not satisfied with posterity , So when you run a topology, run by the way dp Just fine , It can verify the degree of penetration 0 The starting point must be better than not entering 0 The starting point is better .  type node=record y,next:longint; end; var n,m:longint; first,dp,goin,q:Array[..]of longint; i:longint; x,y:longint; e:array[..]of node; tot:longint; procedure adde(x,y:longint); begin e[tot].next:=first[x]; e[tot].y:=y; first[x]:=tot; inc(tot); end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure tupu; var head,tail,now:longint; i:longint; begin head:=; tail:=; for i:= to n do if goin[i]= then begin inc(tail); q[tail]:=i; dp[i]:=; end; while head<=tail do begin now:=q[head]; i:=first[now]; while i<>- do begin y:=e[i].y; dp[y]:=max(dp[y],dp[now]+); dec(goin[y]); if goin[y]= then begin inc(tail); q[tail]:=y; end; i:=e[i].next; end; inc(head); end; end; begin read(n,m); for i:= to n do begin first[i]:=-; dp[i]:=; end; for i:= to m do begin read(x,y); inc(goin[y]); adde(x,y); end; tupu; for i:= to n do writeln(dp[i]); end. luoguP1137 38. Luogu P1272 Tree form dp（ difficult ） This question suddenly confused QAQ It's because I don't understand the topic well enough ... The last subtree does not require that the number given at the beginning be kept ... set up dp[x,j] Express With x The number of nodes reserved for the root tree is j The minimum number of edges to delete in the subtree of . dp[x,1]=num[x] num[x] Express x Degrees （ The degree of + The degree of ）. dp[x,j]=min(dp[y,k]+dp[x,j-k]-2,dp[x,j]) One of the most difficult things to understand is "-2" . Think about It is known that With y After the answer for the root , To move to With x Rooted Be sure to keep it x->y This side , and dp[x,j-k] The cost of deleting this edge is included in . And then there's thinking about dp[y,k] Include in x->y This side , You'll find that if he doesn't include , It's not going to be optimal after the transfer , Find out if it contains ,dp[y,k] Again, the cost of deleting this edge is included , But this side is to be kept , So I -2 It means to cut two unnecessary costs .  type node=record y,next:longint; end; var n,p:longint; i:longint; x,y:longint; v:array[..]of boolean; dp:array[..,..]of longint; e:Array[..]of node; tot,root,ans:longint; first:array[..]of longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure adde(x,y:longint); begin e[tot].next:=first[x]; e[tot].y:=y; first[x]:=tot; inc(tot); end; procedure dfs(x:longint); var i,j,k:longint; y:longint; begin i:=first[x]; for j:= to p do dp[x,j]:= << ; while i<>- do begin y:=e[i].y; dfs(y); for j:=p downto do for k:= to j- do dp[x,j]:=min(dp[x,j-k]+dp[y,k]-,dp[x,j]); i:=e[i].next; end; end; begin read(n,p); for i:= to n do begin first[i]:=-; v[i]:=false; end; for i:= to n- do begin read(x,y); adde(x,y); v[y]:=true; inc(dp[x,]); inc(dp[y,]); end; for i:= to n do if not v[i] then root:=i; dfs(root); ans:= <<; for i:= to n do ans:=min(ans,dp[i,p]); writeln(ans); end. luoguP1272 39. Luogu P1373 thinking dp （ difficult ） Because the state is saved with two people's scores, it is bound to tle（mle） So think about switching thinking （ Yes, I see the problem solved ） In the original question k I take p Express , and p++.( In code p no ++) Because state is really only about difference , So the state can be saved by difference . dp[i,j,k,0/1] Express The ending point is (i,j) What's the difference between the two scores k 0 This step is made up of small ones A Walk the 1 Express This step is made by uim Walk the . dp[i,j,k,0]+=dp[i-1,j,k-a[i,j]+p %p,1]+dp[i,j-1,k-a[i,j]+p %p,1] ( Two directions , Calculate the difference , For negative numbers, you can directly +p Handle ) dp[i,j,k,1]+=dp[i-1,j,k+a[i,j] %p,0]+dp[i,j-1,j+a[i,j] %p,0] ( The same as above ) The answer is ans+=dp[i,j,0,1];  const HR=; var n,m,p:longint; i,j,k:longint; cost,ans:longint; dp:array[..,..,..,..]of longint; a:array[..,..]of longint; begin read(n,m,p); for i:= to n do begin for j:= to m do begin read(a[i,j]); if a[i,j]>=p+ then a[i,j]:=a[i,j] mod (p+); dp[i,j,a[i,j],]:=; end; readln; end; for i:= to n do for j:= to m do for k:= to p do begin cost:=k-a[i,j]+p+; if cost>=p+ then cost:=cost-(p+); dp[i,j,k,]:=dp[i,j,k,]+dp[i-,j,cost,]+dp[i,j-,cost,]; if dp[i,j,k,]>=HR then dp[i,j,k,]:=dp[i,j,k,]mod HR; cost:=k+a[i,j]; if cost>=p+ then cost:=cost-(p+); dp[i,j,k,]:=dp[i,j,k,]+dp[i-,j,cost,]+dp[i,j-,cost,]; if dp[i,j,k,]>=HR then dp[i,j,k,]:=dp[i,j,k,]mod HR; end; for i:= to n do for j:= to m do begin ans:=ans+dp[i,j,,]; if ans>=HR then ans:=ans mod HR; end; writeln(ans); end. luoguP1373 40. Luogu P1537 Split the backpack （ tricks , Hard binary optimization knapsack ） The question can be converted to whether it can be spelled out with a given marble t/2 The value of . t+=x*i (1≤i≤6) Because a lot of values are the same , You can consider binary splitting and then directly 01 It's just a backpack .  var two:array[..]of longint; f:array[..]of boolean; t,z,n:longint; x:longint; i,j:longint; a:array[..]of longint; begin two[]:=; for i:= to do two[i]:=two[i-]*; while not eof do begin inc(z); n:=; t:=; for i:= to do begin read(x); t:=t+x*i; for j:= to do if x>=two[j] then begin inc(n); a[n]:=two[j]*i; x:=x-two[j]; end; if x> then begin inc(n); a[n]:=x*i; end; end; if t= then exit; writeln('Collection #',z,':'); if t mod = then begin writeln('Can''t be divided.'); writeln; end else begin f[]:=true; t:=t div ; for j:= to t do f[j]:=false; for i:= to n do for j:=t downto a[i] do if f[j-a[i]] then f[j]:=true; if f[t] then writeln('Can be divided.') else writeln('Can''t be divided.'); writeln; end; end; end. luoguP1537 41. Luogu P1613 Multiply dp （ It's hard ） Look at the problem QAQ Rabbit is a real dish ... set up dp[k,i,j] Express i To j Whether there is 2k Distance of .(bool Array ) dp[k,i,j]=dp[k-1,i,x] and dp[k-1,x,j] Initialization is dp[0,x,y]=1 This dp There's no way to solve the problem ... But you can find this dp after , You can convert the original graph into a graph that can find the shortest path If exist dp[k,i,j]=true that i and j You can connect one The length is 1 The edge of , It means to arrive with a running function . then folyd The shortest path is ok spicy ~ Sometimes I see 2 Think twice ！！！  var n,m:longint; x,y,i,j,k:longint; dp:array[..,..,..]of boolean; dis:array[..,..]of longint; begin read(n,m); for i:= to m do begin read(x,y); dp[,x,y]:=true; end; for k:= to do for x:= to n do for i:= to n do for j:= to n do if (dp[k-,i,x])and(dp[k-,x,j]) then dp[k,i,j]:=true; for i:= to n do for j:= to n do if i<>j then begin for k:= to do if (dp[k,i,j]) then dis[i,j]:=; if dis[i,j]= then dis[i,j]:=maxint; end; for k:= to n do for i:= to n do for j:= to n do if dis[i,k]+dis[k,j]<dis[i,j] then dis[i,j]:=dis[i,k]+dis[k,j]; writeln(dis[,n]); end. luoguP1613 42. Luogu P1681 similar 34( can Ctrl+F lookup “34.”) Basically the same set up f[i,j,0/1] Express With (i,j) A weight of 0/1 Is the maximum side length of the lower right corner Then the maximum side length that can be extended is themax=min(f[i-1,j,1/0],f[i,j-1,1/0],f[i-1,j-1,0/1]) ( Be careful 1 0 Interchangeability of ) f[i,j,a[i,j]]=themax+1;  var n,m:longint; i,j:longint; ans,themax:longint; f:Array[..,..,..]of longint; a:Array[..,..]of longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; begin read(n,m); for i:= to n do begin for j:= to m do begin read(a[i,j]); f[i,j,a[i,j]]:=; end; readln; end; for i:= to n do for j:= to m do begin themax:=min(f[i-,j,-a[i,j]],f[i,j-,-a[i,j]]); themax:=min(themax,f[i-,j-,a[i,j]]); f[i,j,a[i,j]]:=themax+; end; for i:= to n do for j:= to m do if f[i,j,a[i,j]]>ans then ans:=f[i,j,a[i,j]]; writeln(ans); end. luoguP1681 43. Luogu P3800 Monotonic queue optimization dp （ Data structure optimization dp） dp[i,j] It means the first one i layer Located at j The optimal solution of the column dp[i,j]=max(dp[i-1,k]+a[i,j]) (j-t≤k≤j+t) And then I found this dp Can be monotonic queue optimization , You can also scroll through array optimization ... But I'm too lazy to write  var n,m,k,t,c,max:longint; i,j,x,y:longint; head,tail:longint; dp,a:array[..,..]of longint; q:array[..]of longint; begin read(n,m,k,t); for i:= to k do begin read(x,y,c); a[x,y]:=c; end; for i:= to n do begin for j:= to m do q[j]:=; head:=; tail:=; for x:= to t do begin while (dp[i-,x]>=dp[i-,q[tail]])and(tail>) do dec(tail); inc(tail); q[tail]:=x; end; for j:= to m do begin while (q[head]<j-t)and(head<=tail) do inc(head); if t+j<=m then begin while (dp[i-,t+j]>=dp[i-,q[tail]])and(tail>=head) do dec(tail); inc(tail); q[tail]:=t+j; end; if head>tail then dp[i,j]:=a[i,j] else dp[i,j]:=dp[i-,q[head]]+a[i,j]; end; end; for i:= to m do if dp[n,i]>max then max:=dp[n,i]; writeln(max); end. luoguP3800 43 Hot topic !~ 44. Luogu P1417 Sort dp （ greedy +dp） Obviously a simple one 01 knapsack But it's really so easy ？ Also consider the order in which you choose items Consider two adjacent objects i , j The value of and the choice of are i Choose first a[i]-t*b[i]+a[j]-(t+c[i])*b[j] ① j Choose first a[j]-t*b[j]+a[i]-(t+c[j])*b[i] ② Consider choosing first i When it's more valuable ①>② Simplify to b[j]*c[i]<b[i]*c[j] therefore i Choose first i And j You can determine the order of the order Just sort it out  var t,n,ans:int64; i,j:longint; dp,a,b,c:array[..]of int64; function max(a,b:int64):int64; begin if a>b then exit(a) else exit(b); end; procedure qs(l,r:longint); var i,j:longint; t,x,y:int64; begin i:=l; j:=r; x:=b[(l+r)>>]; y:=c[(l+r)>>]; repeat while c[i]*x<b[i]*y do inc(i); while c[j]*x>b[j]*y do dec(j); if i<=j then begin t:=a[i];a[i]:=a[j];a[j]:=t; t:=b[i];b[i]:=b[j];b[j]:=t; t:=c[i];c[i]:=c[j];c[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 read(t,n); for i:= to n do read(a[i]); for i:= to n do read(b[i]); for i:= to n do read(c[i]); qs(,n); for i:= to n do for j:=t downto c[i] do dp[j]:=max(dp[j-c[i]]+a[i]-j*b[i],dp[j]); for i:= to t do ans:=max(ans,dp[i]); writeln(ans); end. luoguP1417 45. Luogu P1057 Stage dp f[i,j] It means to pass on the first i Time The ball is in j The plan in hand f[i,j]=f[i-1,L]+f[i-1,R] L by j Left side R by j To the right of initialization f[0,1]=1 The ball is in before passing 1 Number in the hand answer f[m,1]  var n,m,l,r:longint; i,j:longint; f:array[..,..]of longint; begin read(n,m); f[,]:=; for i:= to m do for j:= to n do begin l:=j-; if l= then l:=n; r:=j+; if r=n+ then r:=; f[i,j]:=f[i-,l]+f[i-,r]; end; writeln(f[m,]); end. luoguP1057 46. Luogu P1122 Tree form dp dp[i] Express With i Is the largest sum of subtrees of roots Initial value dp[i]=cost[i] dp[i]+=max(dp[x],0) ans=max(dp[i]) Pay attention to the y=fa You have to skip the transfer when you're in , Because you can't update the son node with the father node .  type node=record y,next:longint; end; var tot,n,ans:longint; i:longint; x,y:longint; dp,cost,first:array[..]of longint; e:Array[..]of node; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure adde(x,y:longint); begin e[tot].next:=first[x]; e[tot].y:=y; first[x]:=tot; inc(tot); end; procedure dfs(x,fa:longint); var i,y:longint; begin i:=first[x]; while i<>- do begin y:=e[i].y; if y<>fa then dfs(y,x) else begin i:=e[i].next; continue; end; dp[x]:=dp[x]+max(dp[y],); i:=e[i].next; end; end; begin read(n); for i:= to n do begin read(cost[i]); dp[i]:=cost[i]; first[i]:=-; end; for i:= to n- do begin read(x,y); adde(x,y); adde(y,x); end; dfs(,); for i:= to n do ans:=max(ans,dp[i]); writeln(ans); end. luoguP1122 47.51nod 1242 Matrix fast power template problem Fibonacci can use matrix fast power optimization  type arr=array[..,..]of int64; const HR=; t:arr=((,), (,)); a:arr=((,), (,)); var n:int64; y,f:arr; procedure tonew(n,m:int64;var a:arr;b:arr); var i,j,k:longint; begin for i:= to do for j:= to m do begin for k:= to do begin f[i,j]:=f[i,j]+(a[i,k]*b[k,j] mod n); if f[i,j]>n then f[i,j]:=f[i,j] mod n; end; end; a:=f; for i:= to do for j:= to do f[i,j]:=; end; function power(b,n:int64):int64; begin y:=a; while b> do begin if b and = then tonew(n,,t,y); tonew(n,,y,y); b:=b >> ; end; f[,]:=; f[,]:=; tonew(n,,t,f); exit(t[,]); end; begin read(n); writeln(power(n,HR)); end. 51nod1242 48. Luogu P1108 dp On dp QAQ Look at the problem ... Rabbit The first question is very simple ...dp[i] Represents the length of the longest descending subsequence Second questions : f[i] Express With i The length of the end is dp[i] Number of alternatives f[i]+=f[j] ( if j Can transfer to i namely dp[i]=dp[j]+1 And a[j]>a[i]) But that doesn't take into account the repetitive state , The repetition here is based on the number of subsequences rather than the original subscript of subsequences , So it's not easy to deal with ... consider dp[i]=dp[j] And a[i]=a[j] shows i And j It's actually the same plan , that i It's transferable k It just needs to be added once f[i] Or one more time f[j] Just fine Then force f[j] Set up 0  var sum,ans:int64; dp,f,a:Array[..]of int64; i,j:longint; n:longint; function max(a,b:int64):int64; begin if a>b then exit(a) else exit(b); end; begin read(n); for i:= to n do read(a[i]); a[]:=maxlongint; for i:= to n do begin for j:= to i- do if a[j]>a[i] then dp[i]:=max(dp[i],dp[j]+); end; for i:= to n do ans:=max(ans,dp[i]); f[]:=; for i:= to n do for j:= to i- do begin if (dp[i]=dp[j]+)and(a[j]>a[i]) then f[i]:=f[i]+f[j]; if (dp[i]=dp[j])and(a[i]=a[j]) then f[j]:=; end; for i:= to n do if dp[i]=ans then inc(sum,f[i]); writeln(ans,' ',sum); end. luoguP1108 49. Luogu P1504 01 knapsack The title can be converted to the maximum height that can be spelled out by selecting any building block in the castle Make one for every castle 01 knapsack ,dp[i] Express Can you spell The height is i . And then use one can[i] There are several records The castle can spell the height as i ans by can[i]=n Maximum i  var n:longint; x:longint; i,j:longint; can:Array[..]of longint; dp:Array[..]of boolean; begin read(n); for i:= to n do begin x:=; dp[]:=true; while x>= do begin read(x); if x>= then begin for j:= downto x do if dp[j-x] then dp[j]:=true; end; end; for j:= to do if dp[j] then begin dp[j]:=false; inc(can[j]); end; end; can[]:=n; for j:= downto do if can[j]=n then begin writeln(j); exit; end; end. luoguP1504 50. Luogu P1754 Simple dp The last question is hot , Easy .. dp[i,j] Express front i personal Yes j Yes 50 Yuan's plan dp[i,j]+=dp[i-1,j-1] j>0 dp[i,j]+=dp[i-1,j] i-j>=j then ans+=dp[2*n,i] QAQ Forget to type a statistical answer 2* , therefore wa It's very sad ..  var n:longint; i,j:longint; ans:int64; dp:array[..,..]of int64; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; begin read(n); dp[,]:=; for i:= to *n do for j:= to min(i,n) do begin if j> then dp[i,j]:=dp[i-,j-]; if i-j<=j then inc(dp[i,j],dp[i-,j]); end; for i:= to n do inc(ans,dp[*n,i]); writeln(ans); end. luoguP1754 To be continued ~ End of the flower ~ A hole dug by myself , I have to finish it on my knees ！！！ A hole dug by myself , Finally, I knelt down to make it up ## Dynamic programming dp More related articles on topic exercises 1. Dynamic programming DP The optimization of the Write down what you want to say so that you don't forget .DP The optimization of the . It's about " What is it? "," What's the usage? "," How to use it? " Three aspects . Mainly < Introduction to algorithm competition classic > in ... 2. Dynamic programming dp One . Concept : Dynamic programming dp: It's a mathematical idea of solving decision problems in stages . All in one sentence : Make a big deal small , It's trivial Two . Example 1. Step problem F(10):10 The number of steps therefore :F(10)=F(9)+F(8) F ... 3. Algorithm - Dynamic programming DP Notes Algorithm - Dynamic programming DP Notes Dynamic programming algorithm is a flexible algorithm , Specific problems should be analyzed , Its purpose is to find out the state of the problem to be solved , And then reverse it into solving subproblems , And finally back to the known initial state , Then the solutions of each subproblem are accumulated in order to get ... 4. Monotonic optimization of decision dp Special exercises Monotonic optimization of decision dp Special exercises Summary of optimization methods One . Slope optimization As for the shape \(dp[i]=dp[j]+(i-j)*(i-j)$$ Transfer equation of type , Maintain an upper or lower convex hull , Find the tangent point and solve it quickly Technique : 1. Monotone team ...

5. Pressure dp Topic review

Pressure dp Topic review ( Some questions are too watery , I just jumped ) Skill summary : 1. The selection of a line on a matrix $$n * 2^n$$ D [BZOJ2734][HNOI2012] Set selection I don't think it's good. I think it's difficult ...

6. Tree form dp Special topic summary

Tree form dp Special topic summary vigorously dp My practice and promotion The original questions can be found on the website Skill summary 1. Change the Dafa 2. The state definition should only consider the relationship of influence 3. Data structure and dp Reasonable combination of the two (T11) 4. Many kinds of problems of finding the longest chain can be solved by extracting diameter ( ...

7. Section dp Special exercises

Section dp Special exercises The question 1.Equal Sum Partitions ? This thing ,$$n^2$$ Write it yourself $\$ $\$ 2.You Are the One I feel like I'm being hanged \(dp ...

8. 「 Dynamic programming 」- digit dp project

digit dp, Today, I'm going to talk about a little metaphysics , After class, I took a moment to look at it carefully , I found that the board was very understandable , Just write something here : digit dp The main thing is to do something in the interval , A class of problems in which the number of numbers in the interval satisfies the condition of the problem , The topics are generally easy to understand , At this time ...

9. 【dp project 】NOIP The real question -DP Special exercises

Here's to learn DP The right posture . For ZJOI2019 Go to the water and get ready I'll just write the solution . There will be special exercises and comprehensive exercises in the future . P1005 Matrix access game give $n \times m$ The matrix takes... In each row at a time ...

## Random recommendation

1. mono for android Get photos of your mobile phone or take photos and cut them to save

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

2. iOS Development series --App Extended development

summary from iOS 8 Start Apple Introduced extension (Extension) It is used to enhance the interaction between system application services and applications . It allows you to customize your keyboard . The development of system services, such as system sharing and integration, has become possible .WWDC 2016 Many more ...

3. shell Of if Judge

shell Of if Judge  2012-03-16 14:53:05 classification : Python/Ruby   1 Summary Sometimes you need to specify shell The behavior of implementing different processes depends on the success of the command in the script . if  The structure allows ...

4. jQuery The father of ： Write some code every day

Last fall, , my “ Part time programming project ” There are some problems : If not from Khan Academy If you make time out of your project , I can't make up for the bad progress at all . These projects have encountered some serious problems . I used to work mainly on weekends , Yes ...

5. Import correctly svn Pull the project

Why write this blog ? It mainly records the process of crossing the Yellow River by feeling the stones . Before that eclipse installed svn plug-in unit , Pull Remote Engineering , stay eclipse The project shown , Does not separate the display module project , Instead, It is presented as a general project . Maybe you think that regardless of parting ...

6. PHP in $_FILES How to use it and how to pay attention to it$_FILES: Through HTTP POST Variables submitted to the script when the file is uploaded , Similar to old arrays $HTTP_POST_FILES Array ( Is still valid , But against the use of ) For details, please refer to POST Method upload$_FILES An array of content ...

7. git error

Inquire about git Whether the version of is installed correctly   32 position   64 position

8. JDK 9.0.4 setup script

Because of all kinds of problems , It's because JDK There's something wrong with the version , So I plan to JDK Do it again . Don't see, don't know , I'm scared , I have at least... In my notebook now 5.6 Even more JDK,JRE, And because of years of disrepair , I don't know how these things fit in , ...

9. Django+Echarts Drawing instance

All demonstrations are based on Django2.0 You can read this article : understand Django in aggregate and annotate How to use the function Get one Django+Echarts A complete example of drawing a histogram Requirement specification One will ...

10. Ubuntu Setup after installation root password

installed ubuntu There is no default after root password , If you want to set root The password needs to go through the following steps : 1 sudo passwd 2 Enter the new password twice in a row