盐析白兔

这个屌丝很懒，什么也没留下！

热门标签

动态规划_动态规划csdn

作者：盐析白兔 | 2024-05-13 11:45:02

踩

动态规划csdn

递推：

Tri Tiling

在这里插入图片描述

定义 $f [i] [j]$ 表示填满前 $i$ 列还多 $j$ 个的方案数
边界: $f [0] [0] = f [0] [2] = f [1] [1] = 1$
$f [i] [0] = f [i - 2] [0] + f [i - 1] [1] + f [i - 2] [2]$
$f [i] [1] = f [i - 1] [2]$
$f [i] [2] = f [i] [0] + f [i - 1] [1]$
注意下标越界问题，从 $2$ 开始推

#include <bits/stdc++.h>
using namespace std;
#define maxn 40

int n;long long f[maxn][5];

void readda_() {
	while(scanf("%d",&n)!=EOF) {
		if(n==-1) return ;
		f[0][0]=f[0][2]=f[1][1]=1;
		for(int i=2;i<=n;++i) {
			f[i][0]=f[i-2][0]+f[i-1][1]+f[i-2][2];
			f[i][1]=f[i-1][2];
			f[i][2]=f[i][0]+f[i-1][1];
		}
		printf("%lld\n",f[n][0]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

记忆化搜索：

Function Run Fun

在这里插入图片描述

为了避免重复的子问题，提高效率，我们将遍历过的子问题记录下来

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 30

int a,b,c;
long long f[maxn][maxn][maxn];

long long work_(int x,int y,int z) {
   if(x<=0||y<=0||z<=0) return 1;
   if(x>20||y>20||z>20) return work_(20,20,20);
   if(~f[x][y][z]) return f[x][y][z];
   if(x<y&&y<z) return f[x][y][z]=work_(x,y,z-1)+work_(x,y-1,z-1)-work_(x,y-1,z);
   else {
   	return f[x][y][z]=work_(x-1,y,z)+work_(x-1,y-1,z)+work_(x-1,y,z-1)-work_(x-1,y-1,z-1);
   }
}

void readda_() {
   while(scanf("%d%d%d",&a,&b,&c)!=EOF) {
   	if(a==-1&&b==-1&&c==-1) return ;
   	memset(f,-1,sizeof(f));
   	printf("w(%d, %d, %d) = %lld\n",a,b,c,work_(a,b,c));
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

[SHOI2002]滑雪

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
#define maxn 105
int ans,n,m,a[maxn][maxn],f[maxn][maxn];
int dx[]={0,1,-1,0,0};int dy[]={0,0,0,1,-1};

void dfs_(int x,int y) {
	if(f[x][y]) {
		ans=max(ans,f[x][y]);
		return;
	}
	f[x][y]=1;
	for(int i=1;i<=4;++i) {
		int px=x+dx[i];
		int py=y+dy[i];
		if(px<1||py<1||px>n||py>m) continue;
		if(a[px][py]>=a[x][y]) continue;
		if(!f[px][py]) dfs_(px,py);
		f[x][y]=max(f[x][y],f[px][py]+1);
	}
	ans=max(ans,f[x][y]);
}

void readda_() {
	n=read_();m=read_();
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			a[i][j]=read_();
		}
	}
	memset(f,0,sizeof(f));
	ans=0;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			dfs_(i,j);
		}
	}
	printf("%d",ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

最长递增路径

在这里插入图片描述

先想 $d f s$ ,再记忆化，不难的进一步推出线性方程

线性DP：

[USACO11FEB]属牛的抗议

在这里插入图片描述

定义 $f [i]$ 表示到 $i$ 的最大分组
边界 $f [i] = 0, i f (s [i] > = 0) f [i] = 1$
状态转移：
$i f (f [j]$ && $s [i] - s [j] > = 0)$
$f [i] = m a x (f [i], f [j] + 1)$

#include <bits/stdc++.h>
using namespace std;
#define maxn 1010
int n,s[maxn],f[maxn];
void readda_() {
	n=read_();s[0]=0;
	for(int i=1;i<=n;++i) {
		s[i]=read_();s[i]+=s[i-1];
		if(s[i]>=0) f[i]=1;
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<i;++j) {
			if(f[j]&&s[i]-s[j]>=0)   
			f[i]=max(f[i],f[j]+1);
		}
	}
	if(!f[n]) printf("Impossible");
	else printf("%d",f[n]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

文件排版

在这里插入图片描述

定义 $f [i]$ 表示将第 $i$ 个单词放在当前行的最小难看程度
边界 $f [i] = I N F, f [0] = 0$
状态转移：
$f [i] = m i n (f [i], f [j] + c (i, j))$
注意特判一个单词的情况

三个串的最长公共子序列

显然不是先求两个串的最长公共子序列再与第三个求
反例： $a a a a b b b b c e f g$ 和 $a a b b e f c g$ 和 $a a b b c$
定义 $f [i] [j] [k]$ 表示三个串分别到 $(i, j, k)$ 位置的最长公共子序列
边界 $f [i] [j] [k] = 0$
状态转移：
如果 $a [i]! = b [j]! = c [k]$
$f [i] [j] [k] = m a x (f [i - 1] [j] [k], f [i] [j - 1] [k], f [i] [j] [k - 1])$
如果 $a [i] = = b [j] = = c [k]$
$f [i] [j] [k] = m a x (f [i] [j] [k], f [i - 1] [j - 1] [k - 1])$
如何记录方案呢？
可以开一个 $g$ 数组在转移时记录方案，但是很麻烦。。。
有没有什么高招呢？
将 $f [i] [j] [k]$ 搞成字符串类型

过河+未写待过，数论压缩路径

在这里插入图片描述

花店橱窗布置

在这里插入图片描述

定义 $f [i] [j]$ 表示到第 $i$ 行，最后选第 $j$ 列的最优方案
边界: $f [i] [j] = I N F, f [0] [j] = 0$
状态转移：
$f [i] [j] = m a x (f [i - 1] [k]) + a [i] [j], k < j$
问题的关键是对于每一个 $j$ ，如何找到 $m a x (f [i - 1] [k])$
开一个 $w [i]$ 数组，表示上一行到 $i 列$ 的最大值
$w [i] = m a x (w [i - 1], f [j] [i])$ ， $f [i] [j] = w [j - 1] + a [i] [j]$
如何记录方案呢，开一个 $p r e [i] [j]$ 表示 $f [i] [j]$ 又上一行的第几列转移过来

#include <bits/stdc++.h>
using namespace std;
#define maxn 110
#define maxm 110
int n,m,f[maxn][maxm],a[maxn][maxm],la_w[maxn],la_id[maxn],pre[maxn][maxn],ans[maxn];
void readda_() {
   n=read_();m=read_();
   for(int i=1;i<=n;++i) {
   	for(int j=1;j<=m;++j) {
   		a[i][j]=read_();
   	}
   }
   memset(f,-0x7f,sizeof(f));
   memset(la_w,-0x7f,sizeof(la_w));
   for(int i=1;i<=(m-n+1);++i) {
   	f[1][i]=a[1][i];pre[1][i]=-1;
   	la_w[i]=la_w[i-1];la_id[i]=la_id[i-1];
   	if(f[1][i]>la_w[i]) {
   		la_w[i]=f[1][i];
   		la_id[i]=i;
   	}
   }
   for(int i=2;i<=n;++i) {
   	for(int j=i;j<=(m-n+i);++j) {
   		f[i][j]=la_w[j-1]+a[i][j];
   		pre[i][j]=la_id[j-1];
   	}
   	if(i==n) break;
   	memset(la_w,-0x7f,sizeof(la_w));
   	for(int j=i;j<=(m-n+i);++j) {
   		la_w[j]=la_w[j-1];la_id[j]=la_id[j-1];
   		if(f[i][j]>la_w[j]) {
   			la_w[j]=f[i][j];
   			la_id[j]=j;
   		}
   	}
   }
   int maxd=-2139062143,end;
   for(int i=n;i<=m;++i) if(f[n][i]>maxd) maxd=f[n][i],end=i; 
   printf("%d\n",maxd);ans[n]=end;
   for(int i=n;i>=2;--i) {
   	ans[i-1]=pre[i][end];
   	end=pre[i][end];
   }
   for(int i=1;i<=n;++i) printf("%d ",ans[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

多米诺骨牌

在这里插入图片描述

定义 $f [i] [j]$ 表示到第 $i$ 个牌，第一行和为 $j$ 的最小翻转次数
边界: $f [i] [j] = I N F, f [0] [0] = 0$
状态转移：
$f [i] [j] = m i n (f [i] [j], f [i - 1] [j - a [i]])$
$f [i] [j] = m i n (f [i] [j], f [i - 1] [j - b [i]] + 1)$

#include <bits/stdc++.h>
using namespace std;
#define maxn 1010
#define INF 2139062143
int n,f[maxn][maxn*6],a[maxn],b[maxn],s=0,maxd=0;

void readda_() {
   n=read_();
   for(int i=1;i<=n;++i) {
   	a[i]=read_();b[i]=read_();
   	s+=a[i];s+=b[i];
   	maxd+=max(a[i],b[i]);
   }
   memset(f,0x7f,sizeof(f));
   f[0][0]=0;
   for(int i=1;i<=n;++i) {
   	for(int j=0;j<=maxd;++j) {
   		if(j-a[i]>=0) f[i][j]=min(f[i][j],f[i-1][j-a[i]]);
   		if(j-b[i]>=0) f[i][j]=min(f[i][j],f[i-1][j-b[i]]+1);
   	}
   } 
   int mind=INF,ans=INF;
   for(int i=0;i<=maxd;++i) {
   	if(f[n][i]!=INF) {
   		int AKIOI=abs(i-(s-i));
   		if(AKIOI<mind) {
   			mind=AKIOI;
   			ans=f[n][i];
   		}
   		else if(AKIOI==mind) ans=min(ans,f[n][i]);
   	}
   }
   printf("%d",ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

迷之阶梯

在这里插入图片描述

注意有解的判断，玄学没搞懂 $f [n] > = I N F$

#include <bits/stdc++.h>
using namespace std;
#define maxn 210
int n,a[maxn],f[maxn];
void readda_() {
   n=read_();
   for(int i=1;i<=n;++i) a[i]=read_(); 
   memset(f,0x7f,sizeof(f));
   f[1]=0;
   for(int i=2;i<=n;++i) {
   	for(int j=i-1;j>=2;--j) {
   		for(int k=j-1;k>=1;--k) {
   			if((a[i]-a[k])<=(1<<(j-k))) {
   				f[i]=min(f[i],f[j]+j-k+1);
   			}
   		}
   	}
   }
   if(f[n]>=f[0]) printf("-1");
   else printf("%d",f[n]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

A Spy in the Metro

在这里插入图片描述

先预处理出数组 $h a s$ _ $t r a i n [i] [j]$ 表示表示在 $i$ 时刻在 $j$ 车站有无火车
时间是很好的序，定义 $f [i] [j]$ 表示在时间 $i$ ，在 $j$ 车站的最小等待时间
边界 $f [i] [j] = I N F, f [0] [1] = 0$
状态转移：
有三种决策：
$1 :$ 继续等待： $f [i] [j] = m i n (f [i] [j]), f [i - 1] [j] + 1$
$2 :$ 搭向右开的火车:
$f [i] [j] = m i n (f [i] [j], f [i - t [j - 1]] [j - 1])$
$3 :$ 搭向左开的火车：
$f [i] [j] = m i n (f [i] [j], f [i - t [j]] [j + 1])$
调了很久直接运行错误，以为写炸，结果 $u d e b u g$ 数据范围不对。。。

#include <bits/stdc++.h>
using namespace std;
#define maxt 210
#define maxn 60
#define INF 1061109567

int n,T,t[maxn],m_1,m_2,f[maxt][maxn],d[maxn],cnt=0;
bool has_train[maxt][maxn][3];

inline void clean_() {
   memset(has_train,0,sizeof(has_train));
   memset(f,0x3f,sizeof(f));
}

void readda_() {
   while(scanf("%d",&n)!=EOF) {
   	if(!n) return ;
   	clean_();
   	T=read_();d[0]=0;
   	for(int i=1;i<n;++i) t[i]=read_(),d[i]=d[i-1]+t[i];
   	m_1=read_();int x;
   	for(int i=1;i<=m_1;++i) {
   		x=read_();
   		for(int j=1;j<=n;++j) {
   			has_train[x][j][0]=true;
   			if(j==n) break;
   			x+=t[j];if(x>T) break;
   		} 
   	}
   	m_2=read_();
   	for(int i=1;i<=m_2;++i) {
   		x=read_();
   		for(int j=n;j>=1;--j) {
   			has_train[x][j][1]=true;
   			if(j==1) break;
   			x+=t[j-1];if(x>T) break;
   		}
   	}
   	f[0][1]=0;
   	for(int i=1;i<=T;++i) {
   		for(int j=1;j<=n;++j) {
   			f[i][j]=min(f[i][j],f[i-1][j]+1);
   			if(j>1&&(i-t[j-1])>=0&&has_train[i][j][0])
   			f[i][j]=min(f[i][j],f[i-t[j-1]][j-1]);
   			if(j<n&&(i-t[j])>=0&&has_train[i][j][1])
   			f[i][j]=min(f[i][j],f[i-t[j]][j+1]);
   		}
   	}
   	if(f[T][n]>=INF) printf("Case Number %d: impossible\n",++cnt);
   	else printf("Case Number %d: %d\n",++cnt,f[T][n]);
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

背包：

01背包

烹调方案

在这里插入图片描述

将物品按 $c [x] * b [y] < c [y] * b [x]$ 排序，再 $01$ 背包

#include <bits/stdc++.h>
using namespace std;
#define maxn 60
#define maxT 100010
int n,t;
long long f[maxT],ans=0;
struct node {
	int a,b,c;
}e[maxn];
inline bool cmp_(node aa,node bb) {
	return (long long) aa.c*bb.b < (long long) bb.c*aa.b;
}
void readda_() {
	t=read_();n=read_();
	for(int i=1;i<=n;++i) e[i].a=read_();
	for(int i=1;i<=n;++i) e[i].b=read_();
	for(int i=1;i<=n;++i) e[i].c=read_();
	sort(e+1,e+n+1,cmp_);
	for(int i=1;i<=n;++i) {
		for(int j=t;j>=e[i].c;--j) {
			f[j]=max(f[j],f[j-e[i].c]-(long long)j*e[i].b+e[i].a);
			ans=max(ans,f[j]);
		}
	}
	printf("%lld",ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

小书童——刷题大军

在这里插入图片描述

先求出满足分数情况下的最小时间，在用剩余的时间对题目 $01$ 背包

#include <bits/stdc++.h>
using namespace std;
#define maxn 20
#define maxr 160
int n,m,k,r,a[maxn],c[maxn],w[maxn],f[maxn][maxr];
void readda_() {
	n=read_();m=read_();k=read_();r=read_();
	for(int i=1;i<=n;++i) a[i]=read_();
	for(int i=1;i<=m;++i) c[i]=read_();  
	for(int i=1;i<=m;++i) w[i]=read_();
	memset(f,0x7f,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=m;++i) {
		for(int j=0;j<=k;++j) {
			f[i][j]=min(f[i][j],f[i-1][j]);
			if(j+w[i]<=k) {
				f[i][j+w[i]]=min(f[i][j+w[i]],f[i-1][j+w[i]]);
				f[i][j+w[i]]=min(f[i][j+w[i]],f[i-1][j]+c[i]);
			}
			else {
				f[i][k]=min(f[i][k],f[i-1][k]);
				f[i][k]=min(f[i][k],f[i-1][j]+c[i]);
			}
		}
	}
	r-=f[m][k];
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;++i) {
		for(int j=0;j<=r;++j) {
			f[i][j]=f[i-1][j];
			if(j-a[i]>=0)
			f[i][j]=max(f[i][j],f[i-1][j-a[i]]+1);
		}
	}
	printf("%d",f[n][r]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

[HAOI2012]音量调节

在这里插入图片描述

直接求最大音量不好做，转化为判断性问题
定义 $f [i] [j]$ 表示用前 $i$ 种歌曲，能否达到音量 $j$
边界 $f [i] [j] = 0, f [0] [b e g i n] = 1$
状态转移：
$i f (j - a [i] > = 0) f [i] [j] ∣ = f [i - 1] [j - a [i]]$
$i f (j + a [i] < = m) f [i] [j] ∣ = f [i - 1] [j + a [j]]$

#include <bits/stdc++.h>
using namespace std;
#define maxn 60
#define maxm 1010
int n,b,m,a[maxn],f[maxn][maxm];
void readda_() {
  n=read_();b=read_();m=read_();
  for(int i=1;i<=n;++i) a[i]=read_(); 
  f[0][b]=1;
  for(int i=1;i<=n;++i) {
  	for(int j=0;j<=m;++j) {
  		if(j-a[i]>=0)
  		f[i][j]|=f[i-1][j-a[i]];
  		if(j+a[i]<=m)
  		f[i][j]|=f[i-1][j+a[i]];
  	}
  }
  for(int i=m;i>=0;--i) if(f[n][i]) {printf("%d",i);return;}
  printf("-1");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

完全背包

二维费用背包

榨取kkksc03

在这里插入图片描述

模板题

#include <bits/stdc++.h>
using namespace std;
#define maxn 110
#define maxm 210
#define maxT 210
int n,m,t,a[maxn],b[maxn],f[maxm][maxT];
void readda_() {
	n=read_();m=read_();t=read_();
	for(int i=1;i<=n;++i) {
		a[i]=read_();b[i]=read_();
	}
	for(int i=1;i<=n;++i) {
		for(int j=m;j>=a[i];--j) {
			for(int k=t;k>=b[i];--k) {
				f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+1);
			}
		}
	}
	printf("%d",f[m][t]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

区间DP

[CQOI2007]涂色

在这里插入图片描述

[HNOI2010]合唱队

在这里插入图片描述

[SCOI2003]字符串折叠

在这里插入图片描述

游戏 A Game

在这里插入图片描述

定义 $f [i] [j]$ 为当前玩家对于区间 $[i, j]$ 的最优策略
边界 $f [i] [j] = 0, f [i] [i] = a [i]$
状态转移：
$f [i] [j] = m a x (s u m [i + 1] [j] - f [i + 1] [j] + a [i], s u m [i] [j - 1] - f [i] [j - 1] + a [j])$

#include <bits/stdc++.h>
using namespace std;
#define maxn 110

int n,a[maxn],f[3][maxn],s[maxn];

int main() {
	n=read_();
	for(int i=1;i<=n;++i) {
		a[i]=read_();f[i&1][i]=a[i];
		s[i]=s[i-1]+a[i];
	}
	for(int L=2;L<=n;++L) {
		for(int i=1;(i+L-1)<=n;++i) {
			int j=i+L-1;
			f[i&1][j]=max(s[j]-s[i]-f[(i+1)&1][j]+a[i],s[j-1]-s[i-1]-f[i&1][j-1]+a[j]);
		}
	}
	printf("%d %d",f[1&1][n],s[n]-f[1&1][n]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

[USACO16OPEN]262144

在这里插入图片描述

定义 $f [i] [j]$ 表示左端点为 $j$ ，能合并出数字 $i$ 的右端点的位置
边界 $f [i] [j] = 0, f [x] [i] = i + 1$
状态转移： $f [i] [j] = f [i - 1] [f [i - 1] [j]]$

#include <bits/stdc++.h>
using namespace std;
#define maxn 262200
int n,f[60][maxn];
void readda_() {
   n=read_();
   for(int i=1;i<=n;++i) {
   	int x=read_();
   	f[x][i]=i+1;
   }int ans=0;
   for(int i=2;i<=58;++i) {
   	for(int j=1;j<=n;++j) {
   		if(!f[i][j]) f[i][j]=f[i-1][f[i-1][j]];
   		if(f[i][j]) ans=i;
   	}
   }
   printf("%d",ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

棋盘DP：

Likecloud-吃、吃、吃

在这里插入图片描述

定义 $f [i] [j]$ 为走到 $(i, j)$ 的最大值
边界： $s_x=n+1,s_y=m/2+1$
$f[i][j]=-INF,f[s_x][s_y]=0$
状态转移:
$f [i] [j] = m a x (f [i] [j], f [i + 1] [j] + a [i] [j])$
$f [i] [j] = m a x (f [i] [j], f [i + 1] [j - 1] + a [i] [j])$
$f [i] [j] = m a x (f [i] [j], f [i + 1] [j + 1] + a [i] [j])$

#include <bits/stdc++.h>
using namespace std;
#define maxn 210
int s_x,s_y,n,m,a[maxn][maxn],f[maxn][maxn];
void readda_() {
	n=read_();m=read_();
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			a[i][j]=read_();
		}
	}
	s_x=n;s_y=m/2+1;
	memset(f,-0x7f,sizeof(f));
	f[s_x+1][s_y]=0;
	for(int i=n;i>=1;--i) {
		for(int j=1;j<=m;++j) {
			f[i][j]=max(f[i][j],f[i+1][j]+a[i][j]);
			if(j-1>=1) 
			f[i][j]=max(f[i][j],f[i+1][j-1]+a[i][j]);
			if(j+1<=m)
			f[i][j]=max(f[i][j],f[i+1][j+1]+a[i][j]);
		}
	}
	int maxd=-2139062143;
	for(int i=1;i<=m;++i) maxd=max(maxd,f[1][i]);
	printf("%d",maxd); 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

最大正方形

在这里插入图片描述

定义 $f [i] [j]$ 表示以 $(i, j)$ 为右下角的正方形的最大边长
边界 $f [i] [j] = 0$
状态转移：
$i f (a [i] [j] = = 1)$
$f [i] [j] = m i n (f [i - 1] [j], f [i - 1] [j - 1], f [i] [j - 1]) + 1$
$a n s = m a x (a n s, f [i] [j])$

#include <bits/stdc++.h>
using namespace std;
#define maxn 110
int n,m,f[maxn][maxn],x,ans=0;
void readda_() {
	n=read_();m=read_();
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			x=read_();
			if(x) f[i][j]=min(min(f[i-1][j-1],f[i][j-1]),f[i-1][j])+1;
			ans=max(ans,f[i][j]);
		}
	}
	printf("%d",ans); 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

传纸条

在这里插入图片描述

可以看作两个人从 $(1, 1)$ 走不同路径到 $(n, m)$
很容易想到四维的DP：

#include <bits/stdc++.h>
using namespace std;
#define maxn 100
int f[maxn][maxn][maxn][maxn],n,m,a[maxn][maxn];

void readda_() {
   n=read_();m=read_();
   for(int i=1;i<=n;++i) {
   	for(int j=1;j<=m;++j) {
   		for(int k=1;k<=n;++k) {
   			for(int z=j+1;z<=m;++z) {
   				f[i][j][k][z]=max(max(f[i-1][j][k-1][z],f[i-1][j][k][z-1]),max(f[i][j-1][k-1][z],f[i][j-1][k][z-1]))+a[i][j]+a[k][z];
   			}
   		}
   	}
   }
   printf("%d",f[n][m-1][n-1][m]);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

动归的优化一般就两种：
减少状态数
减少状态转移时间
考虑一个性质，由于两个人走的步数是一样的，所以两个人始终在一条斜线上，该斜线上满足 $(i, j), (k, z)$ , $i + j = k + z = s t e p$
可以将状态压缩至三维 $f [i] [j] [k]$

#include <bits/stdc++.h>
using namespace std;
#define maxn 60
int n,m,a[maxn][maxn],f[maxn<<1][maxn][maxn];

void readda_() {
   n=read_();m=read_();
   for(int len=1;len<=(n+m-1);++len) {
   	for(int i=1;i<=min(len,n);++i) {
   		for(int j=1;j<=min(len,j);++j) {
   			f[len][i][j]=max(max(f[len-1][i][j],f[len-1][i-1][j-1]),max(f[len-1][i-1][j],f[len-1][i][j-1]))+a[i][len-i+1]+a[j][len-j+1];
   			if(i==j) f[len][i][j]-=a[i][len-i+1];
   		}
   	}
   } 
   printf("%d",f[n+m-1][n][n]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

树形DP

工人的请愿书 Another Crisis

在这里插入图片描述

定义 $f [i]$ 表示 $i$ 能向上级发送信息最少需要多少个工人
边界 $f [叶节点] = 1$
状态转移：
$u$ 的儿子数为 $k$ ，则至少需要 $k *$ $T$ %的工人，由于必须是整数，则程序实现为 $(k * T - 1) / 100 + 1$
将儿子的 $f [v]$ 排序， $f [u] + = 前 c 个 f [v]$ , $O : n * l o g (n)$

#include <bits/stdc++.h>
using namespace std;
#define maxn 100050

int n,T,f[maxn];
vector < int > son[maxn];

void dp_(int u) {
	if(son[u].empty()) {f[u]=1;return;}
	for(unsigned int i=0;i<son[u].size();++i) dp_(son[u][i]);
	vector <int > d;
	for(unsigned int i=0;i<son[u].size();++i) d.push_back(f[son[u][i]]);
	int k=son[u].size();
	sort(d.begin(),d.end());
	int c=(k*T-1)/100+1;
	for(int i=0;i<c;++i) f[u]+=d[i];
}

void readda_() {
	while( scanf("%d%d",&n,&T)!=EOF ) {
		if(!n&&!T) return ;
		memset(f,0,sizeof(f));
		for(int i=0;i<=n;++i) son[i].clear();
		int x;
		for(int i=1;i<=n;++i) {
			x=read_();
			son[x].push_back(i);
		}
		dp_(0);
		printf("%d\n",f[0]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Party at Hali-Bula

求树的最大独立集，并判断方案是否唯一？
读入使用 $m a p$ 映射
定义 $f [u] [0 / 1]$ 表示 $u$ 不选或选的最大独立集， $d [u] [0 / 1]$ 表示不选或选方案是否唯一
边界 $f [u] [1] = 1, f [u] [0] = 0, d [u] [0 / 1] = t r u e$
状态转移：
$f [u] [0] + = m a x (f [v] [0], f [v] [1])$
$f [u] [1] + = f [v] [0]$
$d [v] [1] 为 t r u e$ 当且仅当所有的 $d [v] [0]$ 为 $t r u e$
$d [u] [0] 为 t r u e$ 当且仅当所取 $m a x d$ 的 $d [v]$ 为 $t r u e$ ，并且 $f [v] [0]! = f [v] [1]$

#include <bits/stdc++.h>
using namespace std;
#define maxn 250

int n,head[maxn],f[maxn][3],id,sze;
bool d[maxn][3];
map < string , int > p;
struct edge {
	int v,nxt;
}e[maxn<<1];

inline void clean_() {
	memset(head,-1,sizeof(head));
	memset(f,0,sizeof(f));
	memset(d,true,sizeof(d));
	p.clear();
	id=sze=0;
}

inline void add_(int u,int v) {
	e[++sze].v=v;
	e[sze].nxt=head[u];
	head[u]=sze;
}

void dfs_(int u,int fa) {
	f[u][1]=1;f[u][0]=0;
	for(int i=head[u];~i;i=e[i].nxt) {
		int v=e[i].v;
		if(v==fa) continue;
		dfs_(v,u);
		f[u][1]+=f[v][0];
		if(!d[v][0]) d[u][1]=false;
		f[u][0]+=max(f[v][0],f[v][1]);
		if((f[v][0]>f[v][1]&&!d[v][0])||(f[v][1]>f[v][0]&&!d[v][1])||(f[v][0]==f[v][1]))
		d[u][0]=false;
 	}
}

void readda_( ){
	while((scanf("%d",&n))!=EOF) {
		if(!n) return ;
		clean_();
		string a;
		cin >> a;p[a]=++id;
		string b;
		for(int i=1;i<n;++i) {
			cin >> a >> b;
			if(!p[a]) p[a]=++id;
			if(!p[b]) p[b]=++id;
			add_(p[a],p[b]);
			add_(p[b],p[a]);
 		}
 		dfs_(1,0);
 		if(f[1][1]>f[1][0]) {
 			printf("%d ",f[1][1]);
 			if(d[1][1]) printf("Yes\n");
 			else printf("No\n");
		}
		if(f[1][0]>f[1][1]) {
			printf("%d ",f[1][0]);
			if(d[1][0]) printf("Yes\n");
			else printf("No\n");
		}
		if(f[1][0]==f[1][1]) {
			printf("%d No\n",f[1][0]);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/563489