一本通 2.9.3 动态规划中经典题目
1274：【例9.18】合并石子
【题目描述】
在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
计算出将Ｎ堆石子合并成一堆的最小得分。
【题目分析】区间dp
【代码实现】
#include<bits/stdc++.h>
using namespace std;
int n;
int a[105];
int f[105][105];
int main() {
cin >> n;
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] += a[i - 1];
f[i][i] = 0;
}
//len的含义为含有多少个数
for (int len = 2; len <= n; len++) {
//枚举起点，必须保证终点不超出数组范围
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
//枚举中间点
for (int k = i; k < j; k++) {
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1]);
}
}
}
cout << f[1][n];
return 0;
}
1275：【例9.19】乘积最大
【题目描述】
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312， 当N=3，K=1时会有以下两种分法：
1）3*12=36
2）31*2=62
这时，符合题目要求的结果是：31*2=62。
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
【题目分析】区间dp
【代码实现】
#include<bits/stdc++.h>
using namespace std;
int n, k, num;
long long a[15][15], f[15][15];
int b[15];
long long ans;
int main() {
cin >> n >> k >> num;
for (int i = n; i >= 1; i--) {
b[i] = num % 10;
num /= 10;
}
for (int i = 1; i <= n; i++) { //枚举起点
for (int j = i; j <= n; j++) { //枚举终点
a[i][j] = a[i][j - 1] * 10 + b[j];
}
}
// 边界条件
for (int i = 1; i <= n; i++) {
f[i][0] = a[1][i];
}
for (int k1 = 1; k1 <= k; k1++) {
for (int i = k1 + 1; i <= n; i++) {
for (int j = k1; j + 1 <= i; j++) {
f[i][k1] = max(f[i][k1], f[j][k1 - 1] * a[j + 1][i]);
}
}
}
cout << f[n][k] << endl;
return 0;
}
1276：【例9.20】编辑距离
【题目描述】
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符。
对任意的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。
【题目分析】表格dp
【代码实现】
#include <bits/stdc++.h>
using namespace std;
#define N 2005
int dp[N][N];
int main() {
string s1, s2;
cin >> s1 >> s2;
int l1 = s1.length(), l2 = s2.length();
for (int i = 1; i <= l1; ++i)
dp[i][0] = i;
for (int j = 1; j <= l2; ++j)
dp[0][j] = j;
for (int i = 1; i <= l1; ++i)
for (int j = 1; j <= l2; ++j) {
if (s1[i - 1] == s2[j - 1]) //第i与第j字符，在字符串中下标从0开始
dp[i][j] = dp[i - 1][j - 1];
else//添加 删除 修改
dp[i][j] = min(min(dp[i][j - 1] + 1, dp[i - 1][j] + 1), dp[i - 1][j - 1] + 1);
}
cout << dp[l1][l2];
return 0;
}
1277：【例9.21】方格取数
【题目描述】
设有N×N的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：
某人从图中的左上角A出发，可以向下行走，也可以向右行走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。
【题目分析】表格dp
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int n, f[15][15][15][15], m[15][15];
int ans = 0;
int main() {
cin >> n;
//输入数据
int a, b, c;
while (cin >> a >> b >> c, a + b + c != 0) {
m[a][b] = c;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
for (int l = 1; l <= n; l++) {
int maxa = max(f[i - 1][j][k - 1][l], f[i][j - 1][k][l - 1]);
int maxb = max(f[i - 1][j][k][l - 1], f[i][j - 1][k - 1][l]);
int mm = max(maxa, maxb) + m[i][j];
if (i != k && j != l) mm += m[k][l];
f[i][j][k][l] = mm;
}
}
}
}
cout << f[n][n][n][n];
return 0;
}
1278：【例9.22】复制书稿(book)
【题目描述】
现在要把m本有顺序的书分给k个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三和第四本书给同一个人抄写。
现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。
【题目分析】区间dp
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int m, k1;
int f[505][505];
int a[505], s[505];
int rec[505][505];
void print(int i, int x) { //输出数组a[1]~a[i]中子段和小于等于x的所有子段左右端点（子段长度从小到大）
if (i == 0)
return;
int j, sum = 0;
for (j = i; j >= 1 && sum + a[j] <= x; --j)
sum += a[j];
print(j, x);//输出a[1]~a[j]中的子段
cout << j + 1 << ' ' << i << endl;
}
int main() {
//input data
cin >> m >> k1;
for (int i = 1; i <= m; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= m; i++) {
f[i][1] = s[i];
}
for (int k = 2; k <= k1; k++) {
for (int i = k; i <= m; i++) { //枚举书的数量
for (int j = k - 1; j <= i; j++) {
int maxs = max(f[j][k - 1], s[i] - s[j]);
f[i][k] = min(f[i][k], maxs);
}
}
}
print(m, f[m][k1]);
return 0;
}
1279：【例9.23】橱窗布置(flower)
【题目描述】
假设以最美观的方式布置花店的橱窗，有F束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从11到V顺序编号，V是花瓶的数目，编号为11的花瓶在最左边，编号为V的花瓶在最右边，花束可以移动，并且每束花用11到F的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果i<j，则花束i必须放在花束j左边的花瓶中。
例如，假设杜鹃花的标识数为11，秋海棠的标识数为22，康乃馨的标识数为33，所有的花束在放人花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶中只能放一束花。
每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放人不同的花束时会产生不同的美学效果，并以美学值(一个整数)来表示，空置花瓶的美学值为00。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下表格表示。
根据表格，杜鹃花放在花瓶22中，会显得非常好看，但若放在花瓶44中则显得很难看。
为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：1≤F≤100，F≤V≤100，−50≤Aij≤50，其中Aij是花束i摆放在花瓶j中的美学值。输入整数F，V和矩阵(Aij)，输出最大美学值和每束花摆放在各个花瓶中的花瓶编号。
【题目分析】区间dp
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int f, v, a[105][105];
int dp[105][105];
/*
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20
*/
int rec[105][105];
int main() {
//input data
cin >> f >> v;
for (int i = 1; i <= f; i++) {
for (int j = 1; j <= v; j++) {
cin >> a[i][j];
dp[i][j] = -100;
}
}
for (int i = 1; i <= f; i++) {
for (int j = i; j <= v; j++) {
for (int k = i; k <= j; k++) {
if (dp[i][j] < dp[i - 1][k - 1] + a[i][k]) {
dp[i][j] = dp[i - 1][k - 1] + a[i][k];
rec[i][j] = k;
}
}
}
}
// for (int i = 1; i <= f; i++) {
// for (int j = 1; j <= v; j++) {
// cout << rec[i][j] << " ";
// }
// cout << endl;
// }
cout << dp[f][v] << endl;
int b[105], cnt = 0;
int x = f, y = v;
while (x != 0) {
b[++cnt] = rec[x][y];
y = rec[x][y] - 1, x--;
}
for (int i = cnt; i >= 1; i--) {
cout << b[i] << " ";
}
return 0;
}
1280：【例9.24】滑雪
【题目描述】
小明喜欢滑雪，因为滑雪的确很刺激，可是为了获得速度，滑的区域必须向下倾斜，当小明滑到坡底，不得不再次走上坡或等着直升机来载他，小明想知道在一个区域中最长的滑坡。滑坡的长度由滑过点的个数来计算，区域由一个二维数组给出，数组的每个数字代表点的高度。下面是一个例子：
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小，在上面的例子中，一条可行的滑坡为25-24-17-16-1（从25开始到1结束），当然25-24……2-1更长，事实上这是最长的一条。
【题目分析】表格dp
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int m, n;
int a[105][105];
int dp[105][105];
int _next[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dfs(int x, int y) {
if(dp[x][y]>0) return dp[x][y];
dp[x][y]=1;
for (int l = 0; l <= 3; l++) {
int nx = x + _next[l][0];
int ny = y + _next[l][1];
if (nx < 1 || ny < 1 || nx > m || ny > n) continue;
if (a[nx][ny] >= a[x][y]) continue;
dp[x][y] = max(dp[x][y], dfs(nx,ny) + 1);
}
return dp[x][y];
}
int main() {
//input data
cin >> m >> n;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
}
}
int ans = -1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
ans = max(ans, dfs(i,j));
}
}
cout << ans << endl;
return 0;
}
1297：公共子序列
【题目描述】
我们称序列Z=<z1,z2,...,zk>是序列X=<x1,x2,...,xm>的子序列当且仅当存在严格上升的序列<i1,i2,...,ik>，使得对j=1,2,...,k,有xij=zj。比如Z=<a,b,f,c> 是X=<a,b,c,f,b,c>的子序列。
现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。
【题目分析】 LCS 表格dp
【代码实现】
#include<bits/stdc++.h>
using namespace std;
#define N 1000
string s1, s2;
int f[N][N], lena, lenb;
int main() {
while (cin >> s1 >> s2) {
memset(f, 0, sizeof(f));
lena = s1.size();
lenb = s2. size();
for (int i = 1; i <= lena; i++) {
for (int j = 1; j <= lenb; j++) {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (s1[i - 1] == s2[j - 1])
f[i][j] = max(f[i - 1][j - 1] + 1, f[i][j]);
}
}
printf("%d\n", f[lena][lenb]);
s1.clear();
s2.clear();
}
return 0;
}
1298：计算字符串距离
【题目描述】
对于两个不同的字符串，我们有一套操作方法来把他们变得相同，具体方法为：
修改一个字符（如把“a”替换为“b”）;
删除一个字符（如把“traveling”变为“travelng”）。
比如对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。无论增加还是减少“g”，我们都仅仅需要一次操作。我们把这个操作所需要的次数定义为两个字符串的距离。
给定任意两个字符串，写出一个算法来计算出他们的距离。
【题目分析】
类似 1276：【例9.20】编辑距离
【代码实现】
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define M 3000
int f[M][M];
int len_a, len_b;
char a[M], b[M];
int main() {
int t;
scanf("%d", &t);
getchar();
while (t--) {
memset(f, 0, sizeof(f));
scanf("%s", a);
getchar();
scanf("%s", b);
len_a = strlen(a);
len_b = strlen(b);
for (int i = 1; i <= len_a; i++) f[i][0] = i;
for (int i = 1; i <= len_b; i++) f[0][i] = i;
for (int i = 1; i <= len_a; i++) {
for (int j = 1; j <= len_b; j++) {
if (a[i - 1] == b[j - 1]) {
f[i][j] = f[i - 1][j - 1];
} else f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
}
}
printf("%d\n", f[len_a][len_b]);
}
return 0;
}
1299：糖果
【题目描述】
由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。在这一天，Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。糖果公司的N件产品每件都包含数量不同的糖果。Dzx希望他选择的产品包含的糖果总数是K的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然，在满足这一条件的基础上，糖果总数越多越好。Dzx最多能带走多少糖果呢？
注意：Dzx只能将糖果公司的产品整件带走。
【题目分析】表格dp
【代码实现】
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, k;
int a[105];
int dp[105][105];
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
dp[0][0] = 0;
for (int i = 1; i < k; i++) {
dp[0][i] = -INF;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < k; j++) {
dp[i][j] = max(dp[i-1][j], dp[i - 1][(j + k - a[i] % k) % k] + a[i]);
// int m = (j + a[i]) % k;
// dp[i][m] = max(dp[i - 1][m], dp[i - 1][j] + a[i]);
}
}
cout << dp[n][0] << endl;
return 0;
}
1300：鸡蛋的硬度
【题目描述】
最近XX公司举办了一个奇怪的比赛：鸡蛋硬度之王争霸赛。参赛者是来自世界各地的母鸡，比赛的内容是看谁下的蛋最硬，更奇怪的是XX公司并不使用什么精密仪器来测量蛋的硬度，他们采用了一种最老土的办法--从高度扔鸡蛋--来测试鸡蛋的硬度，如果一次母鸡下的蛋从高楼的第a层摔下来没摔破，但是从a+1层摔下来时摔破了，那么就说这只母鸡的鸡蛋的硬度是a。你当然可以找出各种理由说明这种方法不科学，比如同一只母鸡下的蛋硬度可能不一样等等，但是这不影响XX公司的争霸赛，因为他们只是为了吸引大家的眼球，一个个鸡蛋从100 层的高楼上掉下来的时候，这情景还是能吸引很多人驻足观看的，当然，XX公司也绝不会忘记在高楼上挂一条幅，写上“XX公司”的字样--这比赛不过是XX 公司的一个另类广告而已。
勤于思考的小A总是能从一件事情中发现一个数学问题，这件事也不例外。“假如有很多同样硬度的鸡蛋，那么我可以用二分的办法用最少的次数测出鸡蛋的硬度”，小A对自己的这个结论感到很满意，不过很快麻烦来了，“但是，假如我的鸡蛋不够用呢，比如我只有1个鸡蛋，那么我就不得不从第1层楼开始一层一层的扔，最坏情况下我要扔100次。如果有2个鸡蛋，那么就从2层楼开始的地方扔……等等，不对，好像应该从1/3的地方开始扔才对，嗯，好像也不一定啊……3个鸡蛋怎么办，4个，5个，更多呢……”，和往常一样，小A又陷入了一个思维僵局，与其说他是勤于思考，不如说他是喜欢自找麻烦。
好吧，既然麻烦来了，就得有人去解决，小A的麻烦就靠你来解决了：）
【题目分析】区间dp
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int n, m;
int dp[105][15];
int main() {
//input data
while (cin >> n >> m) {
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= m; i++) {
dp[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
dp[i][1] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= m; j++) {
for (int k = 1; k <= i; k++) {
dp[i][j] = min(dp[i][j], max(dp[i - k][j], dp[k - 1][j - 1]) + 1);
}
}
}
cout << dp[n][m] << endl;
}
return 0;
}
1301：大盗阿福
【题目描述】
阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
【题目分析】线性dp
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int n, a;
int dp[100005];
int main() {
//input data
int t;
cin >> t;
while (t--) {
memset(dp, 0, sizeof(dp));
cin >> n;
cin >> dp[1];
for (int i = 2; i <= n; i++) {
scanf("%d", &a);
dp[i] = max(dp[i - 1], dp[i - 2] + a);
}
cout << dp[n] << endl;
}
return 0;
}
1302：股票买卖
【题目描述】
最近越来越多的人都投身股市，阿福也有点心动了。谨记着“股市有风险，入市需谨慎”，阿福决定先来研究一下简化版的股票买卖问题。
假设阿福已经准确预测出了某只股票在未来N天的价格，他希望买卖两次，使得获得的利润最高。为了计算简单起见，利润的计算方式为卖出的价格减去买入的价格。
同一天可以进行多次买卖。但是在第一次买入之后，必须要先卖出，然后才可以第二次买入。
现在，阿福想知道他最多可以获得多少利润。
【题目分析】两个线性dp叠加
【代码实现】
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 0x3f3f3f3f;
int n, ab[N], ba[N], a[N];
int maxa, mina;
int main() {
//input data
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
memset(ab, 0, sizeof(ab));
memset(ba, 0, sizeof(ba));
mina = a[1];
for (int i = 2; i <= n; i++) { //以ab[i]为在i的左边区间最大差值
mina = min(mina, a[i]);
ab[i] = max(ab[i - 1], a[i] - mina);
}
maxa = a[n];
for (int i = n - 1; i >= 1; i--) { //以ba[i]为在i的右边区间最大差值
maxa = max(maxa, a[i]);
ba[i] = max(ba[i + 1], maxa - a[i]);
}
int ans = -INF;
for (int i = 1; i < n; i++) {
ans = max(ab[i] + ba[i + 1], ans);
}
cout << ans << endl;
}
return 0;
}
1303：鸣人的影分身
【题目描述】
在火影忍者的世界里，令敌人捉摸不透是非常关键的。我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。
影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。
针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。
那么问题来了，假设鸣人的查克拉能量为M，他影分身的个数最多为N，那么制造影分身时有多少种（用K表示）不同的分配方法？（影分身可以被分配到0点查克拉能量）
【题目分析】表格dp
问题的本质：将i个球放入j个箱子里，允许为空的方案数
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int n, m, f[15][15];
int main() {
//input data
int t;
cin >> t;
while (t--) {
cin >> m >> n;
memset(f, 0, sizeof(f));
for (int j = 0; j <= n; j++) {
f[0][j] = 1;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (i >= j) f[i][j] = f[i][j - 1] + f[i - j][j];
else f[i][j] = f[i][j - 1];
}
}
cout << f[m][n] << endl;
}
return 0;
}
1304：数的划分
【题目描述】
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5； 1，5，1； 5，1，1；
问有多少种不同的分法。 输出一个整数，即不同的分法。
【题目分析】表格dp
将不能为空转化为允许为空的问题
【代码实现】
#include <bits/stdc++.h>
using namespace std;
int n, k;
int f[200][10];
int main() {
//input data
cin >> n >> k;
int m = n - k;
for (int i = 0; i <= k; i++) {
f[0][i] = 1;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= k; j++) {
if (i >= j) f[i][j] = f[i][j - 1] + f[i - j][j];
else f[i][j] = f[i][j - 1];
}
}
cout << f[m][k] << endl;
return 0;
}
1305：Maximum sum
【题目描述】
【题目分析】两个线性dp的叠加
【代码实现】
#include <bits/stdc++.h>
using namespace std;
/*
1
10
1 -1 2 2 3 -3 4 -4 5 -5
*/
int t, n, a[50005];
int f1[50005], f2[50005];
int main() {
//input data
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
memset(f1, 0, sizeof(f1));
memset(f2, 0, sizeof(f2));
f1[1] = a[1];
for (int i = 2; i <= n; i++) { //从前往后求最大连续子段和
f1[i] = max(f1[i - 1] + a[i], a[i]);
}
for (int i = 2; i <= n; i++) {
f1[i] = max(f1[i - 1], f1[i]);
}
f2[n] = a[n]; //从后往前求最大连续子段和
for (int i = n - 1; i >= 1; i--) {
f2[i] = max(f2[i + 1] + a[i], a[i]);
}
for (int i = n - 1; i >= 1; i--) {
f2[i] = max(f2[i + 1], f2[i]);
}
int ans = f1[1] + f2[2];
for (int i = 2; i <= n - 1; i++) {
ans = max(ans, f1[i] + f2[i + 1]);
}
cout << ans << endl;
}
return 0;
}
1306：最长公共子上升序列
【题目描述】
【题目分析】LCIS 表格dp
【代码实现】
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[505], b[505];
int dp[505][505], rec[505];
int main() {
cin >> m;
for (int i = 1; i <= m; i++) {
scanf("%d", a + i);
}
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%d", b + i);
}
//时间复杂度为O(n^3) 的朴素算法
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a[i] != b[j]) dp[i][j] = dp[i - 1][j];
else {
int mx = 0;
for (int k = 1; k < j; k++)
if (b[j] > b[k] && mx < dp[i - 1][k]) {
mx = dp[i - 1][k];
rec[j] = k;
}
dp[i][j] = mx + 1;
}
}
}
//时间复杂度由O(n^3)优化为O(n^2)
// for (int i = 1; i <= m; i++) {
// int mx = 0;
// for (int j = 1; j <= n; j++) {
// if (a[i] != b[j]) dp[i][j] = dp[i - 1][j];
// else dp[i][j] = mx + 1;
// if (a[i] > b[j]) mx = max(mx, dp[i - 1][j]);
// }
// }
int ans = 0; //is ok
int index = 0;
for (int i = 1; i <= n; i++) {
if (ans < dp[m][i]) {
ans = dp[m][i];
index = i;
}
}
cout << ans << endl;
stack<int> sta;
while(index!=0){
sta.push(b[index]);
index=rec[index];
}
while(!sta.empty()) {
cout<<sta.top()<<" ";
sta.pop();
}
return 0;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
2
0- 0
已为社区贡献7条内容
所有评论(0)