算法模板总结——DP部分

为省赛整理的常用算法模板,动态规划部分

01背包

1
2
3
4
5
int dp[MAX_W + 1];
memset(dp, 0, sizeof(dp));
for(int i=0; i<N; ++i)
for(int j=W; j>=w[i]; --j) // 注意逆序,保证前面的是未使用的
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);

多重背包

N 种物品重量和价值和个数分别为 wi, vi, ni,从这些物品中挑出总重量不超过 W 的物品,求所有挑选方案中价值总和最大。
dp[i + 1][j] = max(dp[i][j − k × w[i]] + k × v[i]|0 ≤ k ≤ ni&&k × w[i] ≤ j)
相当于 ni 个 01 背包。

1
2
3
4
5
6
int dp[MAX_W + 1];
memset(dp, 0, sizeof(dp));
for(int i=0; i<N; ++i)
for(int j=0; j<n[i]; ++j) // n[i]个01背包
for(int k=W; k>=w[i]; --k)
dp[k] = max(dp[k], dp[k-w[i]]+v[i]);

经过二进制优化后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dp[MAX_W + 1];
memset(dp, 0, sizeof(dp));
for(int i=0; i<N; ++i) {
int num = n[i];
for(int j=1; j<=num; j<<=1) {
for(int k=W; k>=j*w[i]; --k)
dp[k] = max(dp[k], dp[k-j*w[i]]+j*v[i]);
num-=j;
}
if(num)
for(int k=W; k>=num*w[i]; --k)
dp[k] = max(dp[k], dp[k-num*w[i]]+num*v[i]);
}


完全背包

N 种物品重量和价值分别为 w i , v i ,每种物品无限个,从这些物品中挑出总重量不超过 W 的物品,求所有挑选方案中价值总和最大。

1
2
3
4
5
6
int dp[MAX_W + 1];
memset(dp, 0, sizeof(dp));
for(int i=0; i<N; ++i)
for(int j=w[i]; j<=W; ++j) // 正序
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);

最长公共子序列

二维简单版:

1
2
3
4
5
6
7
8
9
10
11
12
13
int dp[maxn][maxn];
int LCS(string a,string b) {
memset(dp, 0, sizeof(dp));
for(int i=0; i<a.length(); ++i) // a
for(int j=0; j<b.length(); ++j) { // b
if(a[i] == b[j])
dp[i+1][j+1] = dp[i][j] + 1;
else
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
}
return dp[a.length()][b.length()];
}


最长上升子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int a[maxn], dp[maxn]; // a为序列, dp[i]为以a[i]为结尾的最长上升子序列长度
int LIS(int n)
{
int Maxlis = 0; // 最长上升子序列长度
for(int i=0; i<n; ++i) {
dp[i] = 1; // 记得初始化为1
for(int j=0; j<i; ++j)
if(a[i] > a[j])
dp[i] = max(dp[i], dp[j] + 1);
Maxlis = max(Maxlis, dp[i]); // 记得更新Maxlis
}
return Maxlis;
}

优化后,O(nlog(n)) 算法

1
2
3
4
5
6
7
8
9
10
11
int a[maxn], dp[maxn]; // a为序列, dp[i]为以a[i]为结尾的最长上升子序列长度
int LIS(int n)
{
memset(dp,0x3f,sizeof(dp));
for(int i=0;i<n;i++)
{
*lower_bound(dp,dp+i,a[i])=a[i];
}
return lower_bound(dp,dp+n,INF)-dp;
}

其中:
upper_bound,表示使用二分查找返回排序好的数组中值>k的最小的那个元素的指针
lower_bound,表示使用二分查找返回排序好的数组中值>=k的第一个元素的指针


多重部分和

问题描述:有 n 种大小不同的数字 ai,每种 mi 个,判断是否可以从这些数字中选出若干个使他们的和恰好为 K
设 dp[i+1][j] 为前 i 种数加和为 j 时第 i 种数最多能剩余多少个。(不能得到为-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int a[maxn],m[maxn],dp[maxm]; //a表示数,m表示数的个数,dp范围是所有数的和的范围
bool fun(int n,int K) //n表示数字种类,K表示组成的和
{
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for(int i=0; i<n; ++i) { //根据存储方式作出改变
for(int j=0; j<=K; ++j) {
if(dp[j] >= 0) dp[j] = m[i]; // 前i-1个数已经能凑成j了
else if(j < a[i] || dp[j-a[i]] <= 0) dp[j] = -1; // 否则,凑不成j或者a[i]已经用完,则无法满足
else dp[j] = dp[j-a[i]] - 1; // 否则可以凑成
}
}
return dp[K]>=0;
}

博客理解


多重集的组合数

问题描述:有 n 种物品,第 i 种有 ai 个。不同种类的物品可以相互区分但相同种类的物品无法区分。从这些物品中取出 m 个的话,有多少种取法。结果取 Mod。
设 dp[i + 1][j] 为从前 i 个物品取出 j 个的组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int a[maxn],dp[maxn][maxm]; //dp[i+1][j] 表示从i种物品中取出j个的组合数
int T,B; //T表示种类数,B表示取得数目
void fun()
{
for(int i=1; i<=T+1; ++i) dp[i][0] = 1; // 一个都不取
for(int i=1; i<=T; ++i) {
for(int j=1; j<=B; ++j) {
if(j-1-a[i] >= 0)
dp[i+1][j] = (dp[i+1][j-1] + dp[i][j] - dp[i][j-1-a[i]] + MOD) % MOD;
else
dp[i+1][j] = (dp[i+1][j-1] + dp[i][j]) % MOD;
}
}
}

博客理解


划分数问题

有n个无区别的物体,将他们划分成m组,问有多少种划分方法:
定义dp[i][j]为i个物体进行j组划分的方法数,则有:

dp[i][j]=dp[i-1][j]+dp[i][j-1]


数位DP模板

一般是求小于等于数字N的某些特征数字个数,或者是区间[L,R]的之间的某些特征数字个数,后者一般可以转换成求差的方式来做。

数字处理函数:

1
2
3
4
5
6
7
8
9
int f(int num){
int ans;
int pos = 0;
while(num){
digit[++pos]=num%10;
num=num/10;
}
return dfs( pos, s , true );
}

其中:
digit为处理串的每个数位的数值。
s为初始的状态。
如果有其他限定条件,dfs中可以增加参数。

DFS函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
ll dfs(int l,int s,bool jud) //l表示当前处理的位置,s表示状态,jud表示是否是上界的前缀
{
if(l==0) return 1; //l是0还是-1取决于怎样存储数
if(!jud && dp[l][s]!=-1) return dp[l][s]; //排除上界的前缀情况
int len=jud?digit[l]:9;
ll ans=0;
for(int i=0;i<=len;i++)
{
dosomething //表示其他处理条件,比如剔除不符合的部分数 if(i==9 && fo)continue;
ans+=dfs(l-1,new_s(s,d),jud && i==len);
}
return jud ? ans : dp[l][s] = ans; //排除上界前缀和的情况
}

其中:
dp为记忆化数组;
l为当前处理串的第l位(权重表示法,也即后面剩下l+1位待填数);
s为之前数字的状态(如果要求后面的数满足什么状态,也可以再记一个目标状态t之类,for的时候枚举下t);
jud表示之前的数是否是上界的前缀(即后面的数能否任意填)。
for循环枚举数字时,要注意是否能枚举0,以及0对于状态的影响,有的题目前导0和中间的0是等价的,但有的不是,对于后者可以在dfs时再加一个状态变量z,表示前面是否全部是前导0,也可以看是否是首位,然后外面统计时候枚举一下位数。It depends.
于是关键就在怎么设计状态。当然做多了之后状态一眼就可以瞄出来。

前导零的判断:

1
2
3
4
int dfs(bool zero)
......
ans+=dfs(zero&&i==0)//不区分前导零与零
ans+=dfs(zero&&i==0&&l>1)//区分前导零与零