第五章 动态规划
优化都是对代码的一个等价变形,先写朴素版
背包问题
01背包问题
状态表示 $f(i,j)$ :
-
集合
-
所有选法
-
条件:
- 只从前 $i$ 个物品中选
- 总体积 $\le j$
-
属性
max
状态计算:
- 根据包不包含第 $i$ 个物品划分
- 不含 $i$ ,相当于 $f(i-1,j)$
- 含 $i$ ,相当于 $f(i-1,j-V_i)+W_i$
一维版本:
#include<iostream>
using namespace std;
const int N =1010;
int f[N],volume[N],w[N];
int main()
{
int n,v;
scanf("%d%d",&n,&v);
for(int i=1;i<=n;i++){
scanf("%d%d",&volume[i],&w[i]);
}
for(int i=1;i<=n;i++){
for(int j=v;j>=volume[i];j--){
f[j]=max(f[j],f[j-volume[i]]+w[i]);
}
}
cout<<f[v]<<endl;
return 0;
}
完全背包问题
状态表示 $f(i,j)$ :
-
集合
-
所有选法
-
条件:
- 只从前 $i$ 个物品中选
- 总体积 $\le j$
-
属性
max
状态计算:
-
根据包含几个物品 $i$ 划分
-
设包含 $k$ 个,$k\in \left( 0,1,\cdots ,\lfloor \frac{j}{V_i} \rfloor \right)$ ,则 $f\left( i,j \right) =\max \left( f\left( i-1,j-kV_i \right) +kW_i \right)$
-
由于 $f\left( i,j \right) =\max \left( f\left( i-1,j \right) ,f\left( i-1,j-V_i \right) +W_i,f\left( i-1,j-2V_i \right) +2W_i,\cdots \right)$ ,而
$f\left( i,j-V_i \right) =\max \left( \ \ \ \ \ \ \ \ \ \ \ f\left( i-1,j-V_i \right) ,\ \ \ \ \ \ f\left( i-1,j-2V_i \right) +W_i,\cdots \right)$ ,故 $f\left( i,j \right) =\max \left( f\left( i-1,j \right) ,f\left( i,j-V_i \right) +W_i \right)$
一维版本:
#include<iostream>
using namespace std;
const int N =1010;
int dp[N],v[N],w[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&v[i],&w[i]);
}
for(int i=1;i<=n;i++){
for(int j=v[i];j<=m;j++){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[m]<<endl;
return 0;
}
多重背包问题
类似,在循环j时加入个数限制即可
优化:
设第 $i$ 类物品重量为 $w_i$ ,体积为 $v_i$ ,数量上限为 $s_i$ ,则我们可以把选 $0,1,2,…,s_i$ 个物品 $i$ 转换为从 $\lceil \log _2s_i \rceil$ 这么多个新物品拼凑而成。每个新物品的重量为 $2^kw_i$ ,体积为 $2^kv_i$ , $k=1,2,3,…,\lceil \log _2s_i \rceil$ 则原问题转换为新的01背包问题。
#include<iostream>
using namespace std;
const int N =12010,M=2010;
int dp[M],v[N],w[N];
int main()
{
int n,m;
scanf("%d%d", &n, &m);
int cnt=0;
for(int i=1;i<=n;i++){
int vv,ww,ss;
scanf("%d%d%d",&vv,&ww,&ss);
//将s个分成由二进制数组成的基础砝码,最后一个是特别的砝码
//由此转换为01背包问题
int k=1;
while(k<=ss){
cnt++;
v[cnt]=vv*k;
w[cnt]=ww*k;
ss -=k;
k *=2;
}
if(ss>0){
cnt++;
v[cnt]=vv*ss;
w[cnt]=ww*ss;
}
}
n=cnt;
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[m]<<endl;
return 0;
}
分组背包问题
递推式需要在每组中循环,找出最大的那项。
#include<iostream>
using namespace std;
const int N = 110;
int v[N][N],w[N][N],dp[N][N],s[N];
int main()
{
int n,m;
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
for(int j=1;j<=s[i];j++){
scanf("%d%d",&v[i][j],&w[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=dp[i-1][j];//这里要放在k循环的外面,保证每次比较的一致性
for(int k=1;k<=s[i];k++){
if(j-v[i][k]>=0)
dp[i][j]=max(dp[i][j],dp[i-1][j-v[i][k]]+w[i][k]);
}
}
}
cout<<dp[n][m]<<endl;
return 0;
}
线性DP
最长上升子序列
状态表示 $f(i)$ :
-
集合
-
所有以第 $i$ 个数结尾的上升子序列
-
条件:
- 只从前 $i$ 个数中选
- 以 $i$ 结尾
-
属性
max
状态计算:
- 根据结尾前一个数划分
相当于 $f[i]=\text{max}(f[j]+1),j=0,1,2,…,i-1$
最长公共子序列
状态表示 $f(i,j)$ :
-
集合
-
所有由第一个序列前 $i$ 个字母和第二个序列前 $j$ 个字母组成的子序列
-
条件:
- 只从第一个序列前 $i$ 个字母中选
- 只从第二个序列前 $j$ 个字母中选
-
属性
max长度
状态计算:
- 根据 $a[i],b[j]$ 是否存在于那个最长的子序列中划分
- 都不存在,即 $f[i-1][j-1]$
- $i$ 在 $j$ 不在,而 $f[i][j-1]$ 包含 $i$ 在与不在最长的子序列中,即 $f(2)<f[i][j-1]$
- $i$ 不在 $j$ 在,而 $f[i-1][j]$ 包含 $j$ 在与不在最长的子序列中,即 $f(3)<f[i-1][j]$
- $i,j$ 均在,当且仅当$a[i]=b[j]$ ,即 $f[i-1][j-1]+1$
- 综上,又由于$f[i-1][j]<f[i][j],f[i][j-1]<f[i][j]$ ,所以第二三中情况可以用它俩代替
区间DP
合并相邻石子
状态表示 $f(i,j)$ :
-
集合
-
所有将第 $i$ 堆石子到第 $j$ 堆石子合并成一堆石子的合并方式
-
属性
min的合并代价
状态计算:
- 根据最后一次合并所在位置 $k$ 划分
- 有可能是 $i$ 和后面的合并
- 有可能是 $i+1$ 和后面的合并
- 设第一堆的结尾为 $k$ ,则 $k$ 范围为 $[i,j-1]$
注:区间dp需要枚举每个长度进行合并,所以复杂度n的三次方
for (int len = 2; len <= n; len ++ )//对每个区间长度都要进行枚举
for (int i = 1; i + len - 1 <= n; i ++ )
{
int l = i, r = i + len - 1;
f[l][r] = 1e8;
for (int k = l; k < r; k ++ )
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
计数类DP
完全背包问题转化
==转换为完全背包问题==
$f(i,j)$ 表示用前i个正整数,组成后总和为 $j$ 的总方案数
可以根据第 $i$ 个数出现的个数进行划分
$f(i,j)=f(i-1,j)+f(i-1,j-i)+f(i-1,j-2i)+…$
而 $f(i,j-i)=f(i-1,j-i)+f(i-1,j-2i)+…$ ,
所以$f(i,j)=f(i-1,j)+f(i,j-i)$
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N =1010,mod=1e9+7;
LL dp[N];
int main()
{
int n;
cin>>n;
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
dp[j]=(dp[j]+dp[j-i])%mod;
}
}
cout<<dp[n]<<endl;
return 0;
}
第二种:总和是 $i$ ,并且恰好表示成 $j$ 个数的和的方案数
状态表示 $f(i,j)$ :
-
集合
-
所有总和是 $i$ 并且恰好表示成 $j$ 个数的和的方案数
-
属性
数量
状态计算:
- 根据最小值是否为1进行划分
- 是1,则可以表示为 $f(i-1,j-1)$
- 最小值大于1,则每个数都减去1,变成用 $j$ 个数表示总和为 $i-j$ ,即为 $f(i-j,j)$
- 所以递推式为 $f(i,j)=f(i-1,j-1)+f(i-j,j)$
- 最终结果为总和是 $n$ ,并且恰好表示成 $1,2,3,…,n$ 个数的方式,即 $\text{res}=f(n,1)+f(n,2)+…+f(n,n)$
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];
int main()
{
cin >> n;
f[1][1] = 1;
for (int i = 2; i <= n; i ++ )
for (int j = 1; j <= i; j ++ )
f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
int res = 0;
for (int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % mod;
cout << res << endl;
return 0;
}
数位统计DP
==这个暂时跳过了,==
分情况讨论
前缀和思想
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 10;
/*
001~abc-1, 999
abc
1. num[i] < x, 0
2. num[i] == x, 0~efg
3. num[i] > x, 0~999
*/
int get(vector<int> num, int l, int r)
{
int res = 0;
for (int i = l; i >= r; i -- ) res = res * 10 + num[i];
return res;
}
int power10(int x)
{
int res = 1;
while (x -- ) res *= 10;
return res;
}
int count(int n, int x)
{
if (!n) return 0;
vector<int> num;
while (n)
{
num.push_back(n % 10);
n /= 10;
}
n = num.size();
int res = 0;
for (int i = n - 1 - !x; i >= 0; i -- )
{
if (i < n - 1)
{
res += get(num, n - 1, i + 1) * power10(i);
if (!x) res -= power10(i);
}
if (num[i] == x) res += get(num, i - 1, 0) + 1;
else if (num[i] > x) res += power10(i);
}
return res;
}
int main()
{
int a, b;
while (cin >> a >> b , a)
{
if (a > b) swap(a, b);
for (int i = 0; i <= 9; i ++ )
cout << count(b, i) - count(a - 1, i) << ' ';
cout << endl;
}
return 0;
}
状态压缩DP
蒙德里安的梦想
状态压缩DP,一般用二进制进行压缩状态,用一个二进制数压缩状态
参考链接:(77条消息) Acwing291. 蒙德里安的梦想:状态压缩dp_阿正的梦工坊的博客-CSDN博客
朴素版代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int n,m;
const int N =12,M=1<<N;
LL dp[N][M];
bool st[M];
int main()
{
while(cin>>n>>m,n||m){
//预处理,将所有奇数个连续空格的状态置为false
for(int i=0;i< (1<<n);i++){
int cnt=0;
st[i]=true;
for(int j=0;j<n;j++){
if((i>>j)&1){
if(cnt &1)st[i]=false;
cnt=0;
}
else cnt++;
}
if(cnt &1)st[i]=false;
}
memset(dp,0,sizeof dp);//多次询问,需要清零
dp[0][0]=1;
for(int i=1;i<=m;i++){
for(int j=0;j<(1<<n);j++){
for(int k=0;k<(1<<n);k++){
if((j&k)==0 && st[j|k])dp[i][j] +=dp[i-1][k];
}
}
}
cout<<dp[m][0]<<endl;
}
return 0;
}
==去除无效状态的优化写法(还没看懂)==
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];
vector<int> state[M];
bool st[M];
int main(){
while (cin >> n >> m, n || m){
for (int i = 0; i < 1 << n; i ++ ){
int cnt = 0;
bool is_valid = true;
for (int j = 0; j < n; j ++ )
if (i >> j & 1){
if (cnt & 1){
is_valid = false;
break;
}
cnt = 0;
}
else cnt ++ ;
if (cnt & 1) is_valid = false;
st[i] = is_valid;
}
for (int i = 0; i < 1 << n; i ++ ){
state[i].clear();//多次询问,每询问一次,均须初始化,即清空
for (int j = 0; j < 1 << n; j ++ )
if ((i & j) == 0 && st[i | j])
state[i].push_back(j);
}
memset(f, 0, sizeof f);//多次询问,所以需要初始化
f[0][0] = 1;
for (int i = 1; i <= m; i ++ )
for (int j = 0; j < 1 << n; j ++ )
for (auto k : state[j])
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
return 0;
}
最短hamilton路径
状态表示 $f(i,j)$ :
-
集合
-
所有从 $0$ 走到 $j$ ,走的路径状态为 $i$ 的路径
-
$i$ 为状态压缩二进制数,如(110010),表示12走过,34没走,5走过,6没走
-
属性
最小值
状态计算:
- 根据上一个状态 $k$ ,是由哪个 $k$ 转换为 $i$ 并且到达 $j$ 的
- 相当于将状态 $i$ 的第 $j$ 位的1摘掉
- 然后对于剩下的每一位,如果 $i$ 的那一位为1,则需要比较下 $f(i,j)$ 和 $f(i-\left\{j\right\},k)+w[k][j]$ 大小
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 20,M =1<<N;
int dp[M][N];
int w[N][N];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>w[i][j];
}
}
memset(dp,0x3f,sizeof dp);
dp[1][0]=0;
for(int i=1;i<1<<n;i+=2){
for(int j=0;j<n;j++){
if(i>>j &1){
for(int k=0;k<n;k++){
if(i-(1<<j)>>k&1){
dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+w[k][j]);
}
}
}
}
}
cout<<dp[(1<<n)-1][n-1]<<endl;
return 0;
}
树形DP
状态表示 $f(i,0),f(i,1)$ :
-
集合
-
$f(i,0)$ 所有以 $i$ 为根节点,并且 $i$ 不参加舞会的方案数(直接上司下属不同时参加)
-
$f(i,1)$ 所有以 $i$ 为根节点,并且 $i$ 参加舞会的方案数(直接上司下属不同时参加)
-
属性
参加舞会的happy值sum最大值
状态计算:
- 对于 $f(i,0)$ ,为其直接下属参加或不参加的最大值总和,即 $f\left( i,0 \right) =\sum{\max \left( f\left( s_i,0 \right) ,f\left( s_i,1 \right) \right)}$
- 对于 $f(i,1)$ ,即为其直接下属不参加的总和,即 $f\left( i,1 \right) =\sum{f\left( s_i,0 \right)}$
一般代码模板
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N =6010;
int h[N],e[N],ne[N],idx;
int happy[N],dp[N][2];
bool has_father[N];
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u){
dp[u][1]=happy[u];
//标准邻接表遍历
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
dfs(j);
dp[u][0]+=max(dp[j][0],dp[j][1]);
dp[u][1]+=dp[j][0];
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&happy[i]);//从1开始读入
memset(h, -1, sizeof h);
for(int i=0;i<n-1;i++){
int l,k;
scanf("%d%d",&l,&k);
add(k,l);
has_father[l]=true;
}
//找根节点,有时需要
int root=1;
while(has_father[root])root++;
dfs(root);
int res=max(dp[root][0],dp[root][1]);
cout<<res<<endl;
return 0;
}
记忆化搜索
和前面有向图游戏求 $SG$ 函数值类似
思路:
- 先初始化存储搜索范围的结构为-1
- 若不为-1,则可以直接范围
- 根据具体题目搜索
本质就是暴力dfs加上记忆化结构存储
int dp(int x,int y){
if(f[x][y]!=-1)return f[x][y];//若已经记忆过,则直接输出
f[x][y]=1;
//具体搜索过程
for(int i=0;i<4;i++){
int a=x+dx[i],b=y+dy[i];
if(a>=1 && a<=n && b>=1 && b<=m && h[a][b]<h[x][y]){
f[x][y]=max(dp(a,b)+1,f[x][y]);
}
}
return f[x][y];
}