LiaN

是一只废物捏

0%

【题解】动态规划

发表于 更新于 分类于 本文字数： 13k 阅读时长 ≈ 12 分钟
  • 主要内容：
    • 背包问题
      • 01背包：每个物品只能选一次，二维优化成一维，第二层for逆序遍历；
      • 完全背包：每种物品无限个，无限量选取，和01背包的不同–>第二层for顺序遍历
      • 多重背包：每种物品有限个，小数据：增加一层遍历个数的循环；大数据：二进制优化成01背包
      • 分组背包：
    • 线性DP、区间DP

背包问题

  • 动态规划
    • 状态表示：f（i，j）
      • 表示的集合是啥
        • 01背包里面表示的所有满足条件选法的集合
        • 满足的条件
          • 只从前 i 个物品选
          • 选出来的物品的总体积≤ j
      • 表示的集合属性：最大值、最小值、数量
        • 01背包：f（i，j）的值是集合里面所有选法的总价值的最大值
    • 状态计算：集合的划分
      • 选法中不含第 i 个物品 f（ i - 1，j ）， 选法中含第 i 个物品（先把所有选法中 的第i个物品去掉，f（ i - 1，j - vi ）+ wi ，再加上；最终的f（i，j）== 二者中的最大者
      • 原则：不重 （不一定非要满足） 不漏
  • 优化
    • 一般都是对动态规划的代码（方程）做一个等价变形
    • 所以先考虑基本的形式，再做优化

01背包

介绍

AcWing2 01背包问题（模板题）

2. 01背包问题 - AcWing题库

代码（二维）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

const int N=1005;
int n,m;
int v[N],w[N]
int dp[N][N];
//状态表示：从前i个物品选出来价值不超过j的方案集合 
//属性：集合中价值最大值 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>v[i]>>w[i];	
	//初始化:dp[0~n][0]=0,dp[0][0~n]=0;这里可省略
	for(int i=1;i<=n;i++)  //放前i个物品 
		for(int j=1;j<=m;j++){  //体积不超过j 
			dp[i][j]=dp[i-1][j]; //一定可以不妨第i个物品
			//如果要放第i个物品，必须当前物品体积小于j，说明能够放进去
			//所以选择 不放进该物品 和 放进该物品 中取较大者 
			if(j-v[i]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
		}
	cout<<dp[n][m]<<endl;
}

如果要知道哪几个背包放进去：

1
2
3
4
5
6
7
8
9
10
int j=m;	
for(int i=n;i>=1;i--){
	if(dp[i][j]>dp[i-1][j]){
		x[i]=1;j=j-v[i];
	}else{
		x[i]=0;
	}
}
for(int i=1;i<=n;i++)
	cout<<x[i]<<' ';

代码（优化成一维）

  • 因为当前dp[i] [j]只依赖于该行前面的值和上一行的值，j严格递增，所以可以采用滚动数组，覆盖旧值
  • 如果是j的遍历是顺序的话，那么之后的某个值的更新就用到的是新的值，而不是之前的旧值；所以要逆序

1
2
3
4
5
for(int i=1;i<=n;i++)  //放前i个物品 
    for(int j=m;j>=v[i];j--){ //放前i个物品的容量=j ;倒序
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
cout<<dp[m]<<endl;

AcWing3174 砝码称重

题意

N个数中任意选择，每次选择出来的数字之和一共有多少种

思路

有限个数的选择——> 01背包问题

  • 砝码可以放入左边或者右边，设所有砝码的总重量为m。说明重量 j 的取值范围为[ -m,m]
  • 由于下标不能为负数，所以给所有j都加上一共偏移量N；大于N的j即为实际重量大于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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int w[2*N];
bool dp[105][2*N];
int main(){
	ios::sync_with_stdio(false);
	int n,m=0;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i];m+=w[i];
	} 
	//假设放在左边 砝码重量为负，放在右边为整数 
	//dp[i][j]从前i个砝码中选出的重量为j的方案数量，值：是否存在 
	dp[0][0+N]=true;//啥不选的方案存在 
	for(int i=1;i<=n;i++){
		for(int j=-m;j<=m;j++){
			dp[i][j+N]=dp[i-1][j+N];//不选当前第i个砝码
			//选当前第i个砝码
			//选左边
			if(j-(-w[i])<=m) dp[i][j+N]|=dp[i-1][j-(-w[i])+N];
			//选右边,
			if(j-w[i]>=-m) dp[i][j+N]|=dp[i-1][j-w[i]+N]; 
		}
	}
	int ans=0;
	for(int j=1;j<=m;j++){
		if(dp[n][j+N]) ans++;
	}
	cout<<ans<<endl;
}

AcWing1234 倍数区间（再做一遍我也不会

题意

给出的n个数中找3个数，使得这3个数的和是K的倍数，且这个和最大

思路

背包问题实质上就是：组合问题求最优解

给定一堆元素，从中选出一些物品，在满足某种要求的前提（限制条件）下，得到一个最优值

限制条件：3个数，K的倍数

状态表示里面，一般一个限制就是一维

  • 优化：对于( a + b + c )%k；求出数组里面每个数模k的余数，余数相同的为一组，每组取最大的三个数据

代码

  • 如果该题的数据范围不那么大的话(一般思路，虽然过不了)

    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
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e3+10,M=1e3+10;
    int n,m;
    int a[N];
    int dp[N][5][M];
    int main(){
    	ios::sync_with_stdio(false);
    	cin>>n>>m;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	memset(dp,-0x3f,sizeof dp);
    	//从前i个数选0个数模k等于0的方案是存在的，且值=0;
    	//而...不等于0的方案是不合法的，不能让它等于0
    	//因此，赋为最小值 
    	for(int i=0;i<=n;i++) dp[i][0][0]=0;
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=3;j++)
    			for(int k=0;k<m;k++){
    				dp[i][j][k]=max(dp[i-1][j][k],
    					dp[i-1][j-1][((k-a[i])%m+m)%m]+a[i]);
    			}
    	int ans=0;
    	for(int i=1;i<=n;i++) ans=max(ans,dp[i][3][0]);
    	cout<<ans<<endl;
    }

  • 但是这个题的数据范围就是很大，上面dp过不了 所以要优化一下

    1
    2
    #include<bits/stdc++.h>
    //放弃了，这道题解没看懂woc，以后再写

完全背包

总结：对比完全背包和01背包的区别
  • 二维
1
2
3
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包

f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题
  • 一维：只有第二层for循环的顺序不同；01背包是逆序，完全背包是正序

完全背包的特点：

1
2
3
4
5
6
7
for(int i=1;i<=n;i++){//从前i种物品选择
	for(int j=0;j<=m;j++){//总体积不大于j
		for(int k=0;k*v[i]<=j;k++)//每种物品可以选k个
     		dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
    }
}
cout<<dp[n][m]<<endl;
  • 优化一下：

1
2
3
4
5
6
7
8
for(int i=1;i<=n;i++){
	for(int j=0;j<=m;j++){
        dp[i][j]=dp[i-1][j];
		if(v[i]<=j){
			dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
        }
    }
}
  • 再优化成一维
  • 理解对比和01背包的遍历顺序：
    • 01背包问题中，在j - v[i]体积的情况下，里面不能存在v[i]这个物品，也就是说在求状态dp[j]的时候，dp[j -v[i]]还不能被更新过（后面的计算要用到前面的变量，所以在更新后面的时候，前面的数据不能变，所以从后往前），所以dp[j -v[i]]要放在dp[j]后更新，用递减循环的方式实现这个功能。
    • 若内层循环顺序进行的话，就代表了在j-v[i]体积的情况下，里面还存有v[i]这个物品，对于同一件物品，会计算多次，直到有其他物品加入满足最优解 大于一件被计算多次后的值为止。–> 完全背包
1
2
3
4
5
for(int i = 1 ; i<=n ;i++)
   for(int j = v[i] ; j<=m ;j++)//注意了，这里的j是从小到大枚举，和01背包的唯一不一样
   {
           f[j] = max(f[j],f[j-v[i]]+w[i]);
   }

多重背包

模板

多重背包的特点

  • 每种物品有有限个

小数据的简单做法

  • dp[ i ] [ j ]: 选前i种物品且总体积为 j 的方案的集合；方案的数量
  • 状态转移，第i种物品选0，1，2 . . . .s[i]个 
1
2
3
4
for(int i=1;i<=n;i++)
	for(int j=0;j<=m;j++)
		for(int k=0;k<=s[i]&&k*s[i]<=j;k++){
			dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]*k]+w[i]*k);

二进制优化版：二进制分组+01背包

  • 第 i 种物品有s个，就可以把这 s 个物品拆分成 logs 组物品，每组有k个，对每组进行组合能够拼出所有0-s的任意数字

  • 每组物品只能用一次；转换成01背包问题，注意状态数量的大小 N*logS

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
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;//原来的N=1000 * logS=12 
int n,m;
int s[N],v[N],w[N];
int dp[N];
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m;
	int cnt=0;
	//二进制分完组后，每个值都只能选一个，cnt记录一共有多少个可选 
	for(int i=1;i<=n;i++){
		int a,b,s;cin>>a>>b>>s;
		int k=1;//将某个数量s分组，k=1,2,4,8,16...
		while(k<=s){
			cnt++;
			v[cnt]=a*k; //体积
			w[cnt]=b*k; //价值
			s-=k;
			k*=2; 
		}
		if(s>0){
			cnt++;v[cnt]=a*s;w[cnt]=b*s;
		}
	}
	for(int i=1;i<=cnt;i++)
		for(int j=m;j>=0;j--){
			if(j-v[i]>=0)
				dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	cout<<dp[m]<<endl;
}

分组背包

  • 物品N组，每组物品有若干个，每组里面最多选一个
  • 关于这几种背包，写dp[i][j]=max(dp[i][j],dp[i-1][j-xx]+yy)，如果括号里面后者当某个下标==0 能够包含不选第i种物品的情况，可以直接就这么写，如果不能包含，就要先加一句dp[i][j]=dp[i-1][j]然后再if xxx，dp[i][j]=max(dp[i][j],dp[i-1][j-xx]+yy)
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
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m;
int s[N];//存储每组物品的数量
int v[N][N],w[N][N],dp[N][N];
//v[i][j]:第i组第j个物品的体积 
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		for(int j=1;j<=s[i];j++)
			cin>>v[i][j]>>w[i][j];
	}
	for(int i=1;i<=n;i++)//遍历,从前i组物品中选 
		for(int j=0;j<=m;j++){
			for(int k=0;k<=s[i];k++)//从这组物品里选一个 
			 //if不能放在上面的for里面，不然会直接break掉，
			 //导致不会++ 就不会遍历该组后面的物品，
			 //然而该组后面的物品的体积可能小于等于j是能够满足条件的
				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;
}

数字三角形模型

AcWing898 数字三角形

题意

898. 数字三角形 - AcWing题库

思路

  • 整个过程中在不断做决策，到达某一点时，它要么从左上方来到该点，要么从右上方来到该点；注意考虑边缘的情况，初始化dp数组为最小值；注意dp数组的含义，达到路径之和最大并不是一定会走到dp[ N ] [ M ]整个点，而是在最后一行中取最大值

代码

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
#include<bits/stdc++.h>
using namespace std;

const int N=510,INF=1e9;
int a[N][N],dp[N][N];
//dp(i,j)：走到i，j的路径的集合；值为走到i,j的路径之和最大值 

int main(){
	ios::sync_with_stdio(false);
	int n;cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++) cin>>a[i][j];
	
	for(int i=1;i<=n;i++)
		for(int j=0;j<=i+1;j++)
			dp[i][j]=-INF;
	dp[1][1]=a[1][1];	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++)
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
	}
	int res=-INF;
	for(int j=1;j<=n;j++)
		res=max(res,dp[n][j]);
	cout<<res<<endl;
}

AcWing1015 摘花生

题意

思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;

const int N=105;
int t,R,C,dp[N][N];
int main(){
	cin>>t;
	while(t--){
		cin>>R>>C;
		for(int i=1;i<=R;i++)
			for(int j=1;j<=C;j++){
				cin>> dp[i][j];
				dp[i][j]=max(dp[i-1][j],dp[i][j-1])+dp[i][j];
			}
		cout<<dp[R][C]<<endl;	
	}
}

AcWing1027 方格取数

题意

NxN的方格，从左上走到右下，可以取走方格里的数，取走了数就变成0，能走两次。求走两次取得的数字之和最大值

思路

  • 走两次，可以看成同时走，dp[i1,j1,i2,j2]：从（1，1）走到（i1，j1）以及同时从（1，1）走到（i2，j2）的取的数字总和最大值

  • 因为同一个格子可能走两次，数字被取两次，而只有当i1+j1==i2+j2 的时候，才可能走到同一个各自，所以四维可以优化成三维dp[k,i1,i2]；

  • k用来表示：走到（i1,k-i1) (i2,k-i2)；即横纵坐标之和，取值为[2,n+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
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int w[N][N],dp[2*N][N][N];
int main(){
	int n;cin>>n;
	int r,c,v;
	while(cin>>r>>c>>v,r||c||v) w[r][c]=v;
	for(int k=2;k<=n+n;k++){
		for(int i1=1;i1<=n;i1++){
			for(int i2=1;i2<=n;i2++){
				int j1=k-i1,j2=k-i2;
				if(j1>=1&&j1<=n&&j2>=1&&j2<=n){
					int t=w[i1][j1];
					if(i1!=i2) t+=w[i2][j2];
					int& d=dp[k][i1][i2];
					d=max(d,dp[k-1][i1-1][i2-1]+t);//下下 
					d=max(d,dp[k-1][i1][i2]+t); //右右
					d=max(d,dp[k-1][i1][i2-1]+t); //右下 
					d=max(d,dp[k-1][i1-1][i2]+t);//下右 
				}
			}
		}
	}
	cout<<dp[n+n][n][n]<<endl;
}

AcWing275传纸条

题意

NxN的方格，每个方格里有个数，一条路径从左上到右下，另一条路径从右下到走上。求走两次取得的数字之和最大值

思路

  • 一条路径从左上到右下，另一条路径从右下到走上；完全可以等价于从左上到右下走两次，

AcWing 275. 传纸条【附详细证明】 - AcWing

代码

1
//把方格取数那道题改改就好

线性DP

  • DP的时间复杂度一般等于 状态数量 乘以 转移的计算量
  • 下图来源

AcWing 902 最短编辑距离

题意

902. 最短编辑距离 - AcWing题库

思路

  • 将字符串A变成B有三种操作，每次都会选一种（决策），想知道不同决策的最优结果
  • dp[i] [j] 表示：将A的前i个字符变成B的前j个字符的操作集合；注意dp数组的初始化
    • 插入dp[i][j-1]+1
      • 插入之后a[i]与b[j]完全匹配，所以插入的就是b[j] ，那插入之前a[1~i]和b[1~(j-1)]匹配
    • 删除dp[i-1][j]+1
      • 删除a的第i个字符，那么前一个状态就是dp[i-1] [j] ,然后+1
    • 替换dp[i-1][j-1]+1
    • 如果a[i]==b[j]，啥也不干

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N],b[N];
int dp[N][N];//dp[i][j]将A的前i个字母变成B的前j个字母的操作次数 
int main(){
	int n,m;
	cin>>n>>a+1;//使得a从下标1开始存储 
	cin>>m>>b+1;
	for(int i=1;i<=n;i++) dp[i][0]=i;
	for(int i=1;i<=m;i++) dp[0][i]=i;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1];
			else{
				//删除or删除 
				dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
				//or替换				
				dp[i][j]=min(dp[i-1][j-1]+1,dp[i][j]);
			}
		}
	}
	cout<<dp[n][m]<<endl;
}

AcWing1212 地宫寻宝

题意

1212. 地宫取宝 - AcWing题库

思路

今天看到了橙子哥大佬的ppt上面的话，搬下来就是：

“ 动态规划=分治+记录子问题答案以避免重复解决子问题带来的巨大开销。
按照我的理解，对于一件要做 n 个决策的事情，我们想知道不同决策的最优结果（或不同决策的方案数）。如果枚举每个决策的不同选择，根据乘法原理，这样的方案数很大。而如果不同的决策能够到达的局面数较小，那么我们选择不去记录如何决策，而去记录到达某一个局面时的状态，以及思考当前这个局面，做了某个决策后会到达哪些局面。
这样来看，动态规划并不是一种算法，而是一种能够解决一类问题的方法。 ”

  • 回归正题，在这个题的过程中，要不断做决策——》 往下走or往右走 ，选当前宝贝or不选 ， 可以往动态规划的方向上思考
  • 题目最终要求的是走到(n,m)，且选了k件宝贝，并且最大价值为c的方案数；
  • 或许可以根据题目最终要达到的目的 来设置状态数组dp[i][j][u][v]:当走到(i,j)时,已选了u件且当前最大价值时 v 的方案数量
  • 细节：物品的价值可以是0，在初始化时，对于在(1,1)位置，为了用0描述不选第一件物品，可以对所有物品价值做+1处理；如果方案数大于MOD，多于3个MOD相加会爆int，所以每两个方案数相加的时候都要模上MOD
  • 对于dp[i][j][u][v]的状态转移
    • 走到（i，j）时，并没有选当前位置上的物品：
      • 从上往下 走到（i，j）：dp[i-1][j][u][v]
      • 从左往右 走到（i，j）:dp[i][j-1][u][v]
    • 走到（i，j）时，若能够选上当前位置上的物品。说明在到（i，j）之前的最大价值c‘ 必须＜v，同时该物品的价值v == w[i][j]：
      • 从上往下 走到（i，j）：dp[i-1][j][u-1][c']
      • 从左往右 走到（i，j）:dp[i][j-1][u-1][c']
  • 最后对所有走到(n,m)，且选了k件宝贝，并且最大价值为1到C+1的方案数求和

代码

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
#include<bits/stdc++.h>
using namespace std;

const int N=55,M=15,MOD=1000000007;
int n,m,k,dp[N][N][M][M],w[N][N];

int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>w[i][j]; w[i][j]++;
		}
    
	dp[1][1][0][0]=1;  //不选第一件
	dp[1][1][1][w[1][1]]=1; //选第一件
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int u=0;u<=k;u++){
				for(int v=0;v<M;v++){
					dp[i][j][u][v]=(dp[i][j][u][v]+dp[i-1][j][u][v])%MOD;
					dp[i][j][u][v]=(dp[i][j][u][v]+dp[i][j-1][u][v])%MOD;
					if(v==w[i][j]&&u>0){
						for(int c=0;c<w[i][j];c++){
								dp[i][j][u][v]=(dp[i][j][u][v]+dp[i-1][j][u-1][c])%MOD;
								dp[i][j][u][v]=(dp[i][j][u][v]+dp[i][j-1][u-1][c])%MOD;
						}
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<M;i++) ans=(ans+dp[n][m][k][i])%MOD;
	cout<<ans<<endl;
}

AcWing1214 波动数列

题意

1214. 波动数列 - AcWing题库

思路

  • 首先知道一下同余式：

    • 设m是给定的一个正整数，a、b是整数：

    • a和b被m除时有相同的余数：记为a≡b(mod m)，或记为a≡b(m)。这个式子称为模m的同余式

    • 同余式一边的数可以移到另一边，只要改变符号就可以了。若

      则

  • 根据题意，假设数列第一个数是x，则依次有x，x+d1，x+d1+d2… … x+d1+d2+...+d(n-1) 之和 等于s，将其变换处理一下

    因为x可以是任意数，将其分离出来可得：

    所以，只要s%n (已知)与后面那坨%n 同余即可

  • 故就演变成了：给定n-1个di ，取值只能是+a 或者-b，求如何选取这n-1个数 使得满足条件（就是一个组合问题，很像背包问题对叭对）

  • 设 dp[ i ][ j ] 表示选了前i个数di（就是确定了对应每个位置是该+a还是-b），使得i * di之和 %n的余数等于 j 的方案数

    题目最终要求：选了n-1个di，使得i * di 之和%n的余数 等于s%n

  • 状态转移： dp[ i ][ j ] 已经选了 i - 1 个数，再选第 i 个数使得之和 %n的余数为 j 的：

    • 若确定当前要选的第i个数为 +a：dp[i-1][?]
    • 若确定当前要选的第i个数为 -b ：dp[i-1][??]

  • 要确定？和？？，首先设选完前 i-1 个数 的和为 C，一共有n-1个数

    • 若第i个数为+a
      • j ≡ C + (n-i)*a (mod n) （同余式：左边和右边模上n有相同的余数
      • 所以，C ≡ j-(n-i)*a (mod n) ; 同理可以分析-b的情况

  • 总结

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;

const int MOD=100000007;
int n,s,a,b,dp[1005][1005]; 
//x%y要取正的余数 因为j=[1,n-1] 
int getMod(int x,int y){
	return (x%y+y)%y;
}
int main(){
	cin>>n>>s>>a>>b;
	//dp[i][j]：前i项之和模n的余数 等于j的方案 数量
	dp[0][0]=1; //什么都不选是一种方案 
	for(int i=1;i<n;i++){  //注意边界，i有n-1个
		for(int j=0;j<n;j++){  //余数 0~n-1
			dp[i][j]=(dp[i-1][getMod(j-(n-i)*a,n)]+dp[i-1][getMod(j+(n-i)*b,n)])%MOD;
		}
	}
	cout<<dp[n-1][getMod(s,n)]<<endl;	
}

AcWing899 编辑距离

题意

n个长度不超过10的字符串，每次询问给出一个字符串和一个操作次数上限

针对每次询问，求这n个字符串中有多少个 字符串在上限操作次数内经过操作变成询问给出的字符串

操作：单个字符插入、删除、替换

询问m次

思路

代码

区间DP

  • 状态表示的是某一个区间

AcWing282 石子合并

题意

282. 石子合并 - AcWing题库

思路

  • 将第1到N堆石子合并再一起，最后一步一定是将两堆合并在一起
    • 设dp[i] [j]：把第i到j堆合并在一起，那么最后的步骤是将第i到k堆和第k+1到 j 堆合并在一起，然后加上合并这两堆的代价（用前缀和求出）。
  • 区间遍历通常是：遍历区间长度+左端点
  • 将数组赋值最大memset(a,0x3f,sizeof a);

代码

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
#include<bits/stdc++.h>
using namespace std;
const int N=310;
int INF=1e9; 
int s[N];
//dp[i][j]:将第i到j堆合并的方案集合 
int dp[N][N];
int main(){
	ios::sync_with_stdio(false);
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];s[i]+=s[i-1];
	} 
//	for(int i=0;i<=n;i++)
//		for(int j=0;j<=n;j++) dp[i][j]=INF;
	memset(dp,0x3f,sizeof dp);
	for(int i=1;i<=n;i++) dp[i][i]=0;
	//第一层遍历的是区间大小,“将一堆合并”并不需要代价 人家本来就是一堆 
	for(int len=2;len<=n;len++){
		for(int l=1;l+len-1<=n;l++){  //第二层遍历左端点 
			int r=l+len-1;  //根据区间大小得到右端点 
			for(int k=l;k<=r-1;k++){  //区间内遍历  
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
			}
		}
	} 
	cout<<dp[1][n]<<endl;
}

计数类DP

数位统计DP

状态压缩DP