机试day12
动态规划：用于求解最优解问题，算法与分治法类似，基本思想也是将待求解问题分解成若干字问题，先求解子问题，然后从这些子问题的解得到原问题的解
与分治法不同在于适合用动态规划求解的问题，经分解得到的子问题往往不是相互独立的，若用分治法来解决这类问题，则分解得到的子问题数目太多，有些子问题会被重复计算多次
eg：斐波那契数列递归求解，如果用原来的递归方法会产生很多不必要的运算，例如Fibonacci(7)=F(6)+F(5)，而计算F(6)又会再计算F(5)
为了避免重复计算，可以用一个数组dp来记录计算的中间结果
N阶楼梯上楼问题
N阶楼梯上楼问题_牛客题霸_牛客网 (nowcoder.com)
描述
N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归）
输入描述：
输入包括一个整数N,(1<=N<90)。
输出描述：
可能有多组测试数据，对于每组数据， 输出当楼梯阶数是N时的上楼方式个数。
#include <iostream>
using namespace std;
const int MAXN = 90;
int dp[MAXN];
void get_upstair() {
dp[0] = 1, dp[1] = 2;
for (int i = 2; i < MAXN; i++)
dp[i] = dp[i-1] + dp[i-2];
}
int main() {
get_upstair();
int N;
while (cin >> N)
cout << dp[N-1] << endl;
}dp最好使用long long类型，因为结果可能十分大
最大连续子序列：在一个给定序列中找出一个连续的子序列，使得这个连续的子序列的和最大，输出最大的序列和
最大序列和
描述
给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。 对于S的所有非空连续子序列T，求最大的序列和。 变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。
输入描述：
第一行为一个正整数N，第二行为N个整数，表示序列中的数。
输出描述：
输入可能包括多组数据，对于每一组输入数据， 仅输出一个数，表示最大序列和。
思路：还是用dp数组存储每个位置当前最大的序列和，每次取max(当前值，上一个最大序列和值+当前值)
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N;
while (cin >> N) {
long long S[N];
for (int i = 0; i< N; i++)
cin >> S[i];
long long dp[N];
dp[0] = S[0];
for (int i = 1; i < N; i++)
dp[i] = max(S[i], dp[i-1] + S[i]);
sort(dp, dp + N);
cout << dp[N-1] << endl;
}
};最大子矩阵
描述
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 1)子矩阵。 比如，如下4 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。
输入描述：
输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。 再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。 已知矩阵中整数的范围都在[-127, 127]。
输出描述：
输出最大子矩阵的大小。
思路：挺复杂的，比一行的要难得多
- 在输入时顺便计算sum数组，存储该数上方（包括自己）一列的和
- 接着使用三个嵌套循环该数+上方1行、2行。。。的值，这样就可以转换为一行的矩阵，然后就按照上一题做法写
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N;
while (cin >> N) {
int S[N][N], sum[N][N];
for (int i = 0; i< N; i++) {
for (int j = 0; j < N; j++) {
cin >> S[i][j];
if (i != 0)
sum[i][j] = sum[i-1][j] + S[i][j];
else
sum[i][j] = S[i][j];
}
}
int dp[N], arr[N];
int maxn = sum[0][0];
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
for (int k = 0; k < N; k++) {
if (i == 0)
arr[k] = sum[j][k];
else
arr[k] = sum[j][k] - sum[i-1][k];
}
int current = arr[0];
for (int p = 0; p < N; p++) {
if (p == 0)
dp[p] = arr[p];
else
dp[p] = max(arr[p] + dp[p-1], arr[p]);
current = max(dp[p], current);
maxn = max(current, maxn);
}
}
}
cout << maxn << endl;
}
};法2：更简单，复杂度$O(n^3)$
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<vector<int>> v(n, vector<int>(n));
for(int i = 0; i< n; ++i){
for(int j = 0; j < n; ++j){
cin>>v[i][j];
}
}
int ans = INT_MIN;
for(int i = 0; i < n; ++i){//开始下标i
vector<int> sum(n, 0);
for (int j = i; j < n; ++j){//结束下标j
int b = -32767;//注意此处不要初始化过小导致溢出会出现无厘头结果
for(int k = 0; k < n; ++k){//第k行
sum[k] += v[k][j];
b = max(b+sum[k], sum[k]);//空间优化后的状态方程
ans = max(ans, b);//记录递推过程中的最大值即是最后的结果
}
}
}
cout<<ans<<endl;
return 0;
}最大连续子序列
最大连续子序列_牛客题霸_牛客网 (nowcoder.com)
描述
给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。
输入描述：
测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( K< 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。
输出描述：
对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。
思路：在原有求最大序列和基础上增加了难度，要求存储该序列的首部尾部元素值
我存储的是下标，可以直接取值
- 设置flag，判断输入是否全是负数，如果是直接输出
- 不能再用max了，无法判断哪个是更大的，因此用if比较
- head、tail变量存储的是最大序列和对应的序列首部尾部元素下标，tmp_head、tmp_tail变量存储的是上一个元素所在序列首部尾部元素下标，每次都要更新
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int K;
while (cin >> K) {
if (K == 0)
break;
long long S[K];
int flag = 1;
for (int i = 0; i < K; i++) {
cin >> S[i];
if (S[i] >= 0)
flag = 0;
}
if (!flag) {
long long dp[K];
dp[0] = S[0];
long long maxn = S[0];
int head = 0, tail = 0;
int tmp_head = 0, tmp_tail = 0;
for (int i = 1; i < K; i++) {
if (S[i] > dp[i-1] + S[i]) {
dp[i] = S[i];
tmp_head = i, tmp_tail = i;
} else {
dp[i] = dp[i-1] + S[i];
tmp_tail++;
}
if (maxn < dp[i]) {
maxn = dp[i];
head = tmp_head, tail = tmp_tail;
}
}
cout << maxn << " " << S[head] << " " << S[tail] << endl;
} else {
cout << 0 << " " << S[0] << " "<< S[K-1] << endl;
}
}
};改进：不需要tmp变量，tmp_tail其实就是当前循环的i，只需更新head即可，改进后代码如下
long long dp[K];
dp[0] = S[0];
long long maxn = S[0];
int head = 0, tail = 0, tmp_head = 0;
for (int i = 1; i < K; i++) {
if (S[i] > dp[i-1] + S[i]) {
dp[i] = S[i];
tmp_head = i;
} else {
dp[i] = dp[i-1] + S[i];
}
if (maxn < dp[i]) {
maxn = dp[i];
head = tmp_head, tail = i;
}
}最长递增子序列（LIS）：在一个已知序列中，取出若干元素（不必连续）组成一个新的序列，新序列中各个数依旧保持原序列中先后顺序，若此时下标递增，则称此子序列为原序列的一个递增子序列
拦截导弹
描述
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。
输入描述：
每组输入有两行， 第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25）， 第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。
输出描述：
每组输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。
思路：状态转移方程为$dp[i] = max\{1,dp[j]+1|j\lt i\&\& A_j\ge A_i\}$
#include <iostream>
using namespace std;
int main() {
int k;
while (cin >> k) {
int S[k];
for (int i = 0; i < k; i++) {
cin >> S[i];
}
int dp[k], answer = 0;
for (int i = 0; i < k; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (S[i] <= S[j])
dp[i] = max(dp[i], dp[j] + 1);
}
answer = max(answer, dp[i]);
}
cout << answer << endl;
}
}最大上升子序列和
最大上升子序列和_牛客题霸_牛客网 (nowcoder.com)
描述
一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18，为子序列(1, 3, 5, 9)的和. 你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和为100，而最长上升子序列为(1, 2, 3)。
输入描述：
输入包含多组测试数据。 每组测试数据由两行组成。第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000（可能重复）。
输出描述：
对于每组测试数据，输出其最大上升子序列和。
思路：上一题改编即可，确保是大于而不是大于等于，同时dp取得是最大上升子序列和而不是最长上升子序列长度，只需在满足大于条件后，取==上一个最大上升子序列和==、==前面每个数对应最大上升子序列和+当前值==中的最大值
#include <iostream>
using namespace std;
int main() {
int N;
while (cin >> N) {
int S[N];
for (int i = 0; i < N; i++) {
cin >> S[i];
}
int dp[N], answer = 0;
for (int i = 0; i < N; i++) {
dp[i] = S[i];
for (int j = 0; j < i; j++) {
if (S[i] > S[j])
dp[i] = max(dp[i], dp[j]+S[i]);
}
answer = max(answer, dp[i]);
}
cout << answer << endl;
}
}合唱队形
描述
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK， 则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入描述：
输入的第一行是一个整数N（2 <= N <= 100），表示同学的总数。 第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。
输出描述：
可能包括多组测试数据，对于每组数据， 输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
思路：分成两组，一组从前往后，一组从后往前，最后按照从前往后求数组和并减一，得到最大序列数，总数减它即可
#include <iostream>
using namespace std;
int main() {
int N;
while (cin >> N) {
int T[N];
for (int i = 0; i < N; i++) {
cin >> T[i];
}
int dp1[N], dp2[N], answer = 0;
for (int i = 0; i < N; i++) {
dp1[i] = 1, dp2[N-i-1] = 1;
for (int j = 0; j < i; j++) {
if (T[i] > T[j])
dp1[i] = max(dp1[i], dp1[j] + 1);
}
}
for (int i = N-1; i >= 0; i--) {
for (int j = N-1; j > i; j--) {
if (T[i] > T[j])
dp2[i] = max(dp2[i], dp2[j] + 1);
}
}
for (int i = 0; i < N; i++) {
answer = max(answer, dp1[i]+dp2[i]-1);
}
cout << N - answer << endl;
}
}最长公共子序列（LCS）：给定两个字符串，求一个最长公共子串，同时为两者的子串，且长度最长
思路：
- dp[i][j]表示以s1[i]作为结尾和以s2[i]作为结尾的最长公共子序列长度
- 两两字符比较，如果一个为空串，dp直接赋0
- 如果俩字符相等，那么就是dp[i-1][j-1] + 1
- 如果俩字符不等，取上一个最大值（i-1和j-1）
Coincidence
Coincidence_牛客题霸_牛客网 (nowcoder.com)
描述
Find a longest common subsequence of two strings.
输入描述：
First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.
输出描述：
For each case, output k – the length of a longest common subsequence in one line.
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, s2;
while (cin >> s1 >> s2) {
int n = s1.size(), m = s2.size();
int dp[n+1][m+1]; // dp[i][j]表示以s1[i]作为结尾和以s2[i]作为结尾的最长公共子序列长度
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
cout << dp[n][m] << endl;
}
}背包问题
- 0-1背包：n件物体，每件物体重$w[i]$，价值$v[i]$，现有容量为m的背包，如何选择使得装入背包价值最大
dp[i][j]表示前i个物体装进容量为j的背包能获得的最大价值，dp[n][m]即为所求
- 对于容量为j的背包，如果不放入第i件物体，问题转换为将前i-1个物体放入容量为j的背包，即dp[i][j]=dp[i-1][j]
- 对于容量为j的背包，如果放入第i件物体，问题转换为将前i-1个物体放入容量为j-w[i]的背包，即dp[i][j]=dp[i-1][j-w[i]]+v[i]
因此取两者最大值为状态转移方程
需要注意j-w[i]不小于0，边界价值dp为0
优化：去除i-1，因为结果只与二维数组的上一行相关，但必须保证每次更新中确认dp[j]时，dp[j-w[i]]尚未被本次更新修改，因此需要采用倒序遍历j的值（从大到小）
完全背包：0-1背包的扩展，每种物体不止可以取一件
- 对于容量为j的背包，如果不放入第i件物体，问题转换为将前i-1个物体放入容量为j的背包，即dp[i][j]=dp[i-1][j]
- 对于容量为j的背包，如果放入第i件物体，此时仍可以取第i个物体，因此dp[i][j]=dp[i][j-w[i]]+v[i]
优化后和0-1一样，但是需要正序遍历j
- 多重背包：0-1背包和完全背包之间的折中，即每种物体既不是只能取一件，也不是能取无穷件，而是最多k件
点菜问题
描述
北大网络实验室经常有活动需要叫外卖，但是每次叫外卖的报销经费的总额最大为C元，有N种菜可以点，经过长时间的点菜，网络实验室对于每种菜i都有一个量化的评价分数（表示这个菜可口程度），为Vi，每种菜的价格为Pi, 问如何选择各种菜，使得在报销额度范围内能使点到的菜的总评价分数最大。 注意：由于需要营养多样化，每种菜只能点一次。
输入描述：
输入的第一行有两个整数C（1 <= C <= 1000）和N（1 <= N <= 100），C代表总共能够报销的额度，N>代表能点菜的数目。接下来的N行每行包括两个在1到100之间（包括1和100）的的整数，分别表示菜的>价格和菜的评价分数。
输出描述：
输出只包括一行，这一行只包含一个整数，表示在报销额度范围内，所点的菜得到的最大评价分数。
#include <iostream>
#include <cstring>
using namespace std;
int main() {
int C, N;
while (cin >> C >> N) {
int Pi[N], Vi[N];
for (int i = 0; i < N; i++) {
cin >> Pi[i] >> Vi[i];
}
int dp[C+1];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; i++) {
for (int j = C; j >= Pi[i]; j--) { // 剩余的价格要大于等于当前物体的价格
dp[j] = max(dp[j], dp[j-Pi[i]] + Vi[i]);
}
}
cout << dp[C] << endl;
}
}最小邮票数
描述
有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。 如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。
输入描述：
有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。
输出描述：
对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。
思路：本题是0-1背包问题的扩展，原来是求最大值，现在是求能放下的最小邮票数目
只需max改为min，v[i]改为1，需要注意初始化赋值不是0而是一个较大的数（题中可以大于20），这时不能用memset赋值，而是要用循环赋值（不然会出现奇怪的数值，是由于memset是对内存值修改）
#include <iostream>
#include <cstring>
using namespace std;
int main() {
int M, N;
while (cin >> M >> N) {
int p[N];
for (int i = 0; i < N; i++) {
cin >> p[i];
}
int dp[M+1];
// memset(dp, 100, sizeof(dp));
for (int i = 0; i <= M; i++) {
dp[i] = 100;
}
dp[0] = 0;
for (int i = 0; i < N; i++) {
for (int j = M; j >= p[i]; j--) {
dp[j] = min(dp[j], dp[j-p[i]] + 1);
}
}
if (dp[M] == 100)
cout << 0 << endl;
else
cout << dp[M] << endl;
}
}珍惜现在，感恩生活
题目：共有资金n元，有m中大米，每种大米价格不等，问最多能采购多少
输入：先输入C，表示C组测试案例；每组测试用例第一行两个整数n、m（1<=n,m<=100），分别表示经费金额和大米种类，然后是m行数据，每行包含三个数p、h、c（1<=p<=20 1<=h<=200 1<=c<=20），分别表示每袋大米的价格、每袋大米的质量、大米的袋数
输出：能够购买的最大质量
思路/原理：
降低每种物体的数目可以降低计算复杂度，因此可以将原物品分组，每组个数为$2^0、2^1...2^{c-1}、k-2^{c}+1$，这样可以通过组合得到0到k之间任意件物体价值重量和，即可转化为0-1背包问题
#include <bits/stdc++.h>
using namespace std;
int main() {
int caseNumber;
cin >> caseNumber;
while (caseNumber--) {
int n, m;
cin >> n >> m;
int p[m], h[m], c[m];
vector<int> v, w;
int number = 0;
for (int i = 0; i < m; i++) {
cin >> p[i] >> h[i] >> c[i];
// 开始分解！！关键
for (int j = 1; j <= c[i]; j<<=1) {
v.push_back(j * h[i]);
w.push_back(j * p[i]);
number++;
c[i] -= j;
}
if (c[i] > 0) {
v.push_back(c[i] * h[i]);
w.push_back(c[i] * p[i]);
number++;
}
}
int dp[n+1];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < number; i++) {
for (int j = n; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
cout << dp[n] << endl;
}
}The Triangle
题目：输入一个数字三角形，计算从顶部到底部选取的路径数字和最大值（类似二叉树从根结点到某个叶子节点）
输入：输入N，代表N行，然后输入数字三角形
输出：路径最大值
样例：
输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出：
30从底部开始，直到根结点（逆向思维），dp[i][j]表示从(i, j)出发到底部路径所有值之和最大值
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
int dp[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < i + 1; j++) {
cin >> dp[i][j];
}
}
for (int i = N - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]);
}
}
cout << dp[0][0] << endl;
}