AcWing基础算法课Level-2 第五讲 动态规划
背包问题
AcWing 2. 01背包问题3018人打卡
AcWing 3. 完全背包问题2749人打卡
AcWing 4. 多重背包问题2552人打卡
AcWing 5. 多重背包问题 II2312人打卡
AcWing 9. 分组背包问题2276人打卡
线性DP
AcWing 898. 数字三角形2531人打卡
AcWing 895. 最长上升子序列2545人打卡
AcWing 896. 最长上升子序列 II1846人打卡
AcWing 897. 最长公共子序列2305人打卡
AcWing 902. 最短编辑距离1893人打卡
AcWing 899. 编辑距离1630人打卡
区间DP
AcWing 282. 石子合并2092人打卡
计数类DP
AcWing 900. 整数划分1609人打卡
数位统计DP
AcWing 338. 计数问题818人打卡
状态压缩DP
AcWing 291. 蒙德里安的梦想1252人打卡
AcWing 91. 最短Hamilton路径1219人打卡
树形DP
AcWing 285. 没有上司的舞会1404人打卡
记忆化搜索
AcWing 901. 滑雪1470人打卡
AcWing 2. 01背包问题
//dp[i+1][j]:从0到i+1这个物品中选出总重量不超过j的物品时总价值的最大值 #include #include using namespace std; int n, s, w[5050], k[5050], dp[5050][5050]; int main(){ cin>>n>>s; for(int i = 0; i < n; i++)cin>>w[i]>>k[i]; for(int i = 0; i < n; i++){ for(int j = 0; j <= s; j++){ if(w[i] <= j)dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+k[i]); else dp[i+1][j] = dp[i][j]; } } cout<AcWing 3. 完全背包问题
//k*v[i]<=j时枚举选k次，用来更新状态 //f[i][j]:从0到i个这些物品中选出总重量不超过j的物品时总价值的最大值 #include using namespace std; const int maxn = 1010; int v[maxn], w[maxn]; //int f[maxn][maxn]; int f[maxn]; int main(){ int n, m; cin>>n>>m; for(int i = 1; i <= n; i++) cin>>v[i]>>w[i]; /*1.TLE for(int i = 1; i <= n; i++) for(int j = 0; j <= m; j++) for(int k = 0; k*v[i]<=j; k++) f[i][j] = max(f[i][j], f[i-1][j-k*v[i]]+k*w[i]); */ /*2.MLE for(int i = 1; i <= n; i++){ for(int j = 0; j <= m; j++){ f[i][j] = f[i-1][j]; if(j-v[i]>=0)//从f[i]选，可以无限选 f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]); } } cout<AcWing 4. 多重背包问题
//拆成01背包 #include using namespace std; const int maxn = 10100; int v[maxn], w[maxn], t; int f[maxn]; int main(){ int n, m; cin>>n>>m; for(int i = 1; i <= n; i++){ int x, y, s; cin>>x>>y>>s; while(s--){ v[++t]=x; w[t]=y; } } for(int i = 1; i <= t; i++) for(int j = m; j >= v[i]; j--) f[j] = max(f[j], f[j-v[i]]+w[i]); cout<AcWing 5. 多重背包问题 II
//2进制优化，复杂度从O(n*s*m)优化到O(n*logs*m) //在一堆苹果选出n个苹果,传统的解法是一个一个地去选,选够n个苹果就停止。这样选择的次数就是n次。现在将这一堆苹果分别按照1,2,4,8,16,.....512分到10个箱子里，那么现在任何一个数字x，都可以用着10堆苹果表示，选择次数<=10 #include using namespace std; const int maxn = 10100; int v[maxn], w[maxn], t; int f[maxn]; int main(){ int n, m; cin>>n>>m; for(int i = 1; i <= n; i++){ int a, b, s; cin>>a>>b>>s; for(int k = 1; k <= s; k *= 2){ v[++t] = a*k; w[t] = b*k; s -= k; } if(s>0){v[++t]=a*s; w[t]=b*s;} } for(int i = 1; i <= t; i++) for(int j = m; j >= v[i]; j--) f[j] = max(f[j],f[j-v[i]]+w[i]); cout<AcWing 9. 分组背包问题
//按照组来转移，每次枚举第i组中所有元素为上一组进行转移即可 //f[i][j]:从0到i组物品中选出总重量不超过j的物品时总价值的最大值 #include using namespace std; const int maxn = 110; int v[maxn][maxn], w[maxn][maxn], s[maxn]; int f[maxn][maxn]; int main(){ int n, m; 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++){ for(int j = 0; j <= m; j++){ f[i][j] = f[i-1][j]; //不选 for(int k = 1; k <= s[i]; k++){ if(j>=v[i][k]){ f[i][j] = max(f[i][j], f[i-1][j-v[i][k]]+w[i][k]); } } } } cout<AcWing 898. 数字三角形
//f[i][j]:从(i,j)出发能获得的最大值 _裸递推 #include #include using namespace std; int n, a[510][510], f[510][510]; int main(){ cin>>n; for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) cin>>a[i][j]; for(int i = n; i >= 1; i--) for(int j = 1; j <= i; j++) f[i][j] = max(f[i+1][j], f[i+1][j+1])+a[i][j]; cout<AcWing 895. 最长上升子序列
//f[i]:到i为止的LIS的长度。 //f[i]=max{1,f[j]+1|j #include using namespace std; int n, a[1010], f[1010], ans; int main(){ cin>>n; for(int i = 1; i <= n; i++)cin>>a[i]; for(int i = 1; i <= n; i++){ int t = 0; for(int j = 1; j < i; j++) if(a[j]AcWing 896. 最长上升子序列 II
//f[i]:长为i的LIS末位的最小值 #include #include #include using namespace std; int f[1000010]; int main(){ memset(f,0x3f,sizeof(f)); int n; cin>>n; for(int i = 1; i <= n; i++){ int x; cin>>x; *lower_bound(f+1,f+n+1,x) = x; } cout<AcWing 897. 最长公共子序列
//f[i][j]表示到a[i]和b[j]为止的lCS。转移，显而易见。 #include using namespace std; int f[1010][1010]; int main(){ int n, m; cin>>n>>m; string a, b; cin>>a>>b; for(int i = 0; i < a.size(); i++){ for(int j = 0; j < b.size(); j++){ if(a[i]==b[j])f[i+1][j+1] = f[i][j]+1; else f[i+1][j+1] = max(f[i][j+1],f[i+1][j]); } } cout<AcWing 902. 最短编辑距离
//题意：给出两个字符串a和b，将a通过删除，插入，替换变换成b，求最少操作次数。 //思路：f[i][j]表示将a[1~i]变成b[1~j]的最小操作次数，转移的时候分别考虑删除，插入和替换即可。 #include using namespace std; const int maxn = 1010; int f[maxn][maxn]; int main(){ int n, m; string a, b; cin>>n>>a>>m>>b; a = "0"+a; b = "0"+b; memset(f,0,sizeof(f)); for(int i = 1; i <= n; i++)f[i][0] = i;//只能删除 for(int i = 1; i <= m; i++)f[0][i] = i;//只能插入 for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);//删除a[i]或插入b[j]使之匹配, 次数+1 if(a[i]==b[j])f[i][j] = min(f[i][j],f[i-1][j-1]);//本来就相等 else f[i][j] = min(f[i][j],f[i-1][j-1]+1);//修改a[i]或b[j] } } cout<AcWing 899. 编辑距离
//题意：给出n个字符串和m个询问，每次询问n个串中有多少个可以在k次操作(插入, 删除, 替换)内变成给出的字符串t //思路：多跑几遍上题的最短编辑距离就行,m*(n*10^2)=1e8 #include using namespace std; const int maxn = 1010; string s[maxn]; //计算次数 int f[maxn][maxn]; int dist(string a, string b){ int n=a.size(), m=b.size(); a = "0"+a; b = "0"+b; //memset(f,0,sizeof(f)); for(int i = 1; i <= n; i++)f[i][0] = i;//只能删除 for(int i = 1; i <= m; i++)f[0][i] = i;//只能插入 for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);//删除a[i]或插入b[j]使之匹配, 次数+1 if(a[i]==b[j])f[i][j] = min(f[i][j],f[i-1][j-1]);//本来就相等 else f[i][j] = min(f[i][j],f[i-1][j-1]+1);//修改a[i]或b[j] } } return f[n][m]; } int main(){ ios::sync_with_stdio(false); int n, m; cin>>n>>m; for(int i = 1; i <= n; i++)cin>>s[i]; for(int i = 1; i <= m; i++){ string t;int k; cin>>t>>k; int ans = 0; for(int i = 1; i <= n; i++) if(dist(s[i], t) <= k)ans++; cout<AcWing 282. 石子合并
#include #include using namespace std; const int maxn = 1010, inf=0xffffff; int w[maxn], f[maxn][maxn]; int main(){ int n; cin>>n; for(int i = 1; i <= n; i++)cin>>w[i]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) f[i][j] = i==j ? 0 : inf; for(int i = 1; i <= n; i++)w[i] += w[i-1]; //转移顺序长度从小到大覆盖即可 for(int i = n; i >= 1; i--)//枚举起点 for(int j = i; j <= n; j++)//枚举终点 for(int k = i; k <= j; k++)//枚举断点 f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+w[j]-w[i-1]); cout<AcWing 900. 整数划分
//题意：给出一个整数n，求其有多少种形如n==n1+n2+..nk的分法，输出划分总数%1e9+7; //思路：把1,2,3,...,n分别看做n个物体的体积,这n个物体均无使用次数限制,问恰好能装满总体积为n的背包的总方案数（完全背包问题变形）。f[i][j]表示用[1-i]的整数拼成j的方案数，转移时考虑能不能选并把值累加一下就行。 #include using namespace std; const int maxn = 1010; const int mod = 1e9+7; int f[maxn][maxn]; int main(){ ios::sync_with_stdio(false); int n; cin>>n; for(int i = 0; i <= n; i++)f[i][0] = 1;//前i个全不选也是一种方案 for(int i = 1; i <= n; i++){//考虑第i个数选不选 for(int j = 1; j <= n; j++){//能拼成数j的方案数 if(j >= i)f[i][j] = (f[i-1][j]+f[i][j-i])%mod;//能选 else f[i][j] = f[i-1][j]%mod;//不能选 } } cout<AcWing 338. 计数问题
//题意：给出两个数a和b，求a和b之间所有数字中0-9的出现次数，a,b<=1e8 //思路：可以通过找规律推出1-n中数字i出现的次数，然后作差。 #include using namespace std; //计算从1到n的整数中数字i出现多少次 int cal(int n, int i){ int len = 0, t=n; while(t){len++; t/= 10;} //计算位数 int ans = 0; //从右到左第j位上(个十百千)，数字i出现多少次 for(int j = 1; j <= len; j++){ //计算第j-1,j,j+1位的数字 int p = pow(10,j-1); int l = n/p/10, r = n%p, dj = n/p%10; //第j位左边的数字小于实际l的情况 if(i)ans += l*p; if(!i && l)ans += (l-1)*p; //第j位左边的数字等于实际l的情况 if((dj>i) && (i||l))ans += p; if((dj==i) && (i||l))ans += r+1; } return ans; } int main(){ ios::sync_with_stdio(false); int a, b; while(cin>>a>>b){ if(a==0 && b==0)break; if(a>b)swap(a,b); for(int i = 0; i <= 9; i++) cout<AcWing 291. 蒙德里安的梦想
/* 题意：把n*m的棋盘分成若干个1*2的长方形，求有多少种方案 思路：首先总的方案数,等价于横着摆放的方案数，所以直接枚举横着的就行。然后如何判断当前方案数是否合法？所有剩余位置能否填充满竖着的小方块。可以按列来看，每一列内部所有连续的空着的小方块需要是偶数个。 状态：f[i][j]表示已经将前i-1列摆好，且从第i−1列，伸出到第i列的状态是j的所有方案，其中j是一个2进制数，表示当前第i列的状态。 状态转移：枚举第(i-1,i)的所有状态j和(i-2,i-1)的所有状态k，如果他们两个不冲突，那就可以从f[i-1,k]转移到f[i,j]。 */ #include using namespace std; typedef long long LL; const int maxn=12; LL ok[1<<12], f[12][1<<12]; int main(){ int n, m; while(cin>>n>>m &&n&&m){ //判断状态i是否合法 for(int i = 0; i < (1<>j)&1==1){ if(cnt%2==1)ok[i]=false; cnt = 0; }else cnt++; } if(cnt%2==1)ok[i] = false; } //dp memset(f,0,sizeof(f)); f[0][0] = 1; for(int i = 1; i <= m; i++){ for(int j = 0; j < (1<AcWing 91. 最短Hamilton路径
//f[i][j]表示当前已经走过点的集合为i，当前人站在j（终点），此时的最短路径长度 //转移时用不包含j的集合向当前集合转移，用集合内的点k和边e[k][j]来更新，f[i][j] = min{f[i][j], f[i-(1< using namespace std; const int maxn=30; int e[maxn][maxn], f[1<<20][maxn]; int main(){ ios::sync_with_stdio(false); int n; cin>>n; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin>>e[i][j]; memset(f,0x3f,sizeof(f)); f[1][0] = 0; for(int i = 0; i < (1<>j&1)==1){//j在集合里 for(int k = 0; k < n; k++){ if(((i-(1<>k&1)==1){//走到j这个点之前,以k为终点的最短距离 f[i][j] = min(f[i][j], f[i-(1<AcWing 285. 没有上司的舞会
/* 用f[x][0],f[x][1] 分别表示x没去和去了的最大价值。 f[x][0] = sigmar:max(f[y][0],f[y][1]); f[x][1] = sigmar:f[y][0]; */ #include #include #include #define maxn 6000*2 using namespace std; int n, r[maxn], f[maxn][2], in[maxn]; vectorG[maxn]; void dp(int x){ f[x][1] = r[x]; for(int i = 0; i < G[x].size(); i++){ int y = G[x][i]; dp(y); f[x][0] += max(f[y][0],f[y][1]); f[x][1] += f[y][0]; } } int main(){ cin>>n; for(int i = 1; i <= n; i++)cin>>r[i]; for(int i = 1; i < n; i++){ int a, b; cin>>a>>b; G[b].push_back(a); in[a]++; } int head = 0; //找树根,即入度为0的结点 for(int i = 1; i <= n; i++) if(in[i]==0){ head = i; break; } dp(head); cout<AcWing 901. 滑雪
//f[i][j]:以(i,j)为终点的最长路是是多少 //f[i][j] = f(它四周的比他高的方块的最长路)+1 #include #include using namespace std; const int maxn = 550; int r, c, a[maxn][maxn], f[maxn][maxn], ans; const int dx[] = {1,0,-1,0}; const int dy[] = {0,-1,0,1}; bool inside(int x, int y){return x>=1&&x<=r&&y>=1&&y<=c;} int dp(int x, int y){ if(f[x][y])return f[x][y]; int res = 0; for(int i = 0; i < 4; i++){ int nx = x+dx[i], ny = y+dy[i]; if(inside(nx,ny)&&a[nx][ny]>a[x][y]){ res = max(res,dp(nx,ny)); } } return f[x][y]=res+1;//我竟然因为没有更新f[x][y]导致第二个点没过。。 } int main(){ ios::sync_with_stdio(false); cin>>r>>c; for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) cin>>a[i][j]; for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) ans = max(ans,dp(i,j)); cout<
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
