有较复杂限制条件的dp（CF366C，POJ1837，CF294B题解+总结）

前言

这篇文章将用三道 精选的好题 例题让你学会这种类型的题目。

题型

看起来是一个背包，但是多了一个条件，是一个等式或不等式，有时候式子还挺复杂的，该怎么办呢？

例题1 CF366C Dima and Salad

题意

原题
有 n n n个水果可以用来做沙拉，每种水果有它的美味值 a i a_i ai​和卡路里 b i b_i bi​，假设选中了的 m m m个水果编号为 1 1 1到 m m m，则满足 ∑ j = 1 m a j ∑ j = 1 m b j = k \frac{\sum_{j=1}^{m}a_j}{\sum_{j=1}^{m}b_j}=k ∑j=1m​bj​∑j=1m​aj​​=k，求美味值的最大总和。如果无法选出至少一个水果满足上述条件，输出-1。

思路

看着除法就难受，先将表示条件的等式两边都乘上 ∑ j = 1 m b j \sum_{j=1}^{m}b_j ∑j=1m​bj​，得 ∑ j = 1 m a j = k ∑ j = 1 m b j \sum_{j=1}^{m}a_j=k\sum_{j=1}^{m}b_j ∑j=1m​aj​=k∑j=1m​bj​。再把右边的式子变成 0 0 0，得 ∑ j = 1 m a j − k ∑ j = 1 m b j = 0 \sum_{j=1}^{m}a_j-k\sum_{j=1}^{m}b_j=0 ∑j=1m​aj​−k∑j=1m​bj​=0。这就变得很好转移了：每多选一个水果 i i i，式子左边就加上 a i − k b j a_i-k b_j ai​−kbj​。
可以设计 d p i , j dp_{i,j} dpi,j​表示选到第 i i i个水果， ∑ j = 1 m a j − k ∑ j = 1 m b j = j \sum_{j=1}^{m}a_j-k\sum_{j=1}^{m}b_j=j ∑j=1m​aj​−k∑j=1m​bj​=j的情况下最大的美味值总和。初始值是没选任何一个水果， d p 0 , 0 = 0 dp_{0,0}=0 dp0,0​=0，答案是所有水果都判断完了且满足题目中式子， d p n , 0 dp_{n,0} dpn,0​。转移很简单，到了水果 i i i要么选，要么不选， j j j的变动也已经讲过了，具体实现请看代码。

代码

由于数组下标不能为负，所以 j j j要加上 a d d add add，数组整体向右平移

#include<bits/stdc++.h>
using namespace std;
#define add 50000
int n,k,a[105],b[105],dp[105][100005];
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	memset(dp,-0x3f,sizeof(dp));
	dp[0][add]=0;
	for(int i=1;i<=n;i++)
		for(int j=-add;j<=add;j++){
			if(dp[i-1][j+add]>=0) dp[i][j+add]=dp[i-1][j+add];
			if(dp[i-1][j-(a[i]-k*b[i])+add]>=0&&abs(j-(a[i]-k*b[i]))<=add)
			//确保在数组下标在界内且用于更新当前状态的dp值存在（初始值是-0x3f3f3f3f）
				dp[i][j+add]=max(dp[i][j+add],dp[i-1][j-(a[i]-k*b[i])+add]+a[i]);
		}
	if(dp[n][add]>0) cout<<dp[n][add]<<endl;
	//add相当于0+add，表示j为0的dp值
	else cout<<-1<<endl;
	return 0;
}

还有一种方法，可以把数组按 j j j的正负拆成两半，分成两个数组处理

#include<bits/stdc++.h>
using namespace std;
#define add 50000
int n,k,a[105],b[105],dp[2][105][add];
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	memset(dp,-0x3f,sizeof(dp));
	dp[1][0][0]=0;
	for(int i=1;i<=n;i++)
		for(int j=-add;j<=add;j++){
			int id=1,id2=1;
			if(j<0) id=0;
			if(j-(a[i]-k*b[i])<0) id2=0;
			//id和id2存储前后两个dp状态属于负的一半还是正的一半，方便后面计算
			if(dp[id][i-1][abs(j)]>=0) dp[id][i][abs(j)]=dp[id][i-1][abs(j)];
			if(dp[id2][i-1][abs(j-(a[i]-k*b[i]))]>=0&&abs(j-(a[i]-k*b[i]))<=add) 
				dp[id][i][abs(j)]=max(dp[id][i][abs(j)],dp[id2][i-1][abs(j-(a[i]-k*b[i]))]+a[i]);
		}
	if(dp[1][n][0]>0) cout<<dp[1][n][0]<<endl;
	else cout<<-1<<endl;
	return 0;
}

例题2 POJ1837 Balance

题意

原题
有一个天平（杠杆），上面有 C C C个钩子可以挂砝码，有 G G G个砝码，你必须把所有砝码都挂到钩子上，每个钩子可以挂多个砝码。给出每个钩子到中心（支点）的距离（左侧用负数，右侧用正数，相当于把支点视为原点的一个数轴）和砝码的重量，请问有多少种挂的方式可以使天平平衡。
没好好上小学自然课的戳这里

思路

这里其实有一个隐含，但其实很显然的的等式，设挂了 n n n个砝码，重量是 w i w_i wi​，到支点的距离是 d i d_i di​（这里的定义与题目中相同，左侧的钩子到支点的距离是负数，左右刚好可以起到抵消的效果），要使天平平衡，则 ∑ i = 1 n ( w i d i ) = 0 \sum_{i=1}^{n}(w_id_i)=0 ∑i=1n​(wi​di​)=0 （物理常识） 。
这个式子已经是一个右侧等于 0 0 0的式子了，直接把左边塞到 j j j里面： d p i , j dp_{i,j} dpi,j​表示判断到第 i i i个砝码， ∑ i = 1 n ( w i d i ) = j \sum_{i=1}^{n}(w_id_i)=j ∑i=1n​(wi​di​)=j，有多少种挂的方法。转移时枚举这个砝码要挂在哪个钩子上，将砝码 a a a挂在钩子 b b b上会使 j j j增加 w a d b w_ad_b wa​db​，最后的答案就是 d p G , 0 dp_{G,0} dpG,0​。具体请看代码。

代码

和上面一样，数组要向右平移，定义了常量 a d d add add。

#include<iostream>
#include<cmath>
using namespace std;
#define add 7500
int c,g,d[25],w[25];
long long dp[25][15000];
int main(){
	cin>>c>>g;
	for(int i=1;i<=c;i++) cin>>d[i];
	for(int i=1;i<=g;i++) cin>>w[i];
	dp[0][add]=1;
	for(int i=1;i<=g;i++)
		for(int j=-add;j<=add;j++)
			for(int k=1;k<=c;k++)
				if(abs(j-d[k]*w[i])<=add)
					dp[i][j+add]+=dp[i-1][j-d[k]*w[i]+add];
	cout<<dp[g][add]<<endl;
	return 0;
}

例题3 CF294B Shaass and Bookshelf

题意

原题
有 n n n本书，它们的厚度是 1 1 1或 2 2 2，宽度是 w i w_i wi​，高度是一个定值（不用管它），书的摆放方式如下图（先竖着摆，再把剩下的横着放在上面，注意：横着摆的时候不能多本书叠在一起；横着放的书的宽度之和不能大于竖着放的书的厚度之和，即上面的书不能伸出去）

请问竖着放的书的厚度总和最小是多少。

思路

我上课的时候看到这道题，感觉方法简直摆在面前。先把式子揪出来，设放在上面的书编号为 1 1 1到 a a a，竖着放的书编号为 1 1 1到 b b b，需满足不等式： ∑ i = 1 a w i ≤ ∑ i = 1 b h i \sum_{i=1}^{a}w_i\le\sum_{i=1}^{b}h_i ∑i=1a​wi​≤∑i=1b​hi​（ w w w表示宽度， h h h表示厚度），移项： ∑ i = 1 b h i − ∑ i = 1 a w i ≥ 0 \sum_{i=1}^{b}h_i-\sum_{i=1}^{a}w_i\ge0 ∑i=1b​hi​−∑i=1a​wi​≥0。
设计状态： d p i , j dp_{i,j} dpi,j​表示放到第 i i i本书， ∑ i = 1 b h i − ∑ i = 1 a w i = j \sum_{i=1}^{b}h_i-\sum_{i=1}^{a}w_i=j ∑i=1b​hi​−∑i=1a​wi​=j，竖着放的书的厚度总和最小是多少。转移：把书放到上面： j j j减去 w i w_i wi​；把书放在下面： j j j加上 h i h_i hi​， d p dp dp值加上 h i h_i hi​。 好了，就这么解决了，突然有点轻松到不习惯。

代码

#include<bits/stdc++.h>
using namespace std;
#define add 10000
int n,h[105],w[105],dp[105][20005],ans=0x3f3f3f3f;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i]>>w[i];
	memset(dp,0x3f,sizeof(dp));
	dp[0][add]=0;
	for(int i=1;i<=n;i++)
		for(int j=-add;j<=add;j++){
			if(j-h[i]>=-add) 
				dp[i][j+add]=dp[i-1][j-h[i]+add]+h[i];
			if(j+w[i]<=add)
				dp[i][j+add]=min(dp[i][j+add],dp[i-1][j+w[i]+add]);
		}
	for(int i=0;i<=add;i++) ans=min(ans,dp[n][i+add]);
	cout<<ans<<endl;
	return 0;
}

为什么要把式子变形，放入数组的下标中？

• 变形：右边变成常数 0 0 0，好求答案。左边的式子化简，快速求出变化量，好转移。
• 放入 d p dp dp下标：这里说点题外话，dp的本质是什么？在一定的限制之下最大化（最小化）某一个值。 条件和限制一般都会放入下标中（例如01背包中的背包空间）， d p dp dp的值负责存储最优值。

总结

• 把（不）等式找出来，移项后使右边变成 0 0 0
• 把（不）等号左边的式子放进 d p dp dp的某一个维度中，考虑每次转移会对式子造成什么影响
• 如果下标会变成负数，平移或拆分解决

都看到这里了，如果有收获，留个赞呗（逃