实验二：动态规划

1.双11的红包雨

问题描述

双11到了，据说这2天会下红包雨，每个红包有不同的价值，小k好开心，但有个规则，就只能接掉落在他身旁的10米范围内的红包（0-10这11个位置）。小k想尽可能的多抢红包，这样就可以去买一个华为手机，小k每秒种只能在移动不超过一米的范围内接住红包。小k一开始站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的红包。问小k最多可能接到多少价值的红包？

输入

第一行输入整数n，表示共有多少个红包，n<1000；

后面n行表示n个红包，每行有三个整数，分别表示红包掉落的位置、时间和价值。

输出

小k接到的红包价值之和。

输入样例

8
3 18 5
7 13 7
1 8 10
2 7 13
10 20 1
3 17 8
10 2 123
3 13 45

输出样例

81

每个时刻的状态只有三种

1. 继续站在原地

2. 向左移动

3. 向右移动

   此外还要注意一点，在0处不能向左移动，在11处不能向右移动。

   状态转移方程
   $$dp[i][j]=maxn(dp[i+1][j-1]，dp[i+1][j]，dp[i+1][j+1])+dp[i][j]$$

#include<bits/stdc++.h>
using namespace std;int dp[1010][12];  // dp[i][j]表示i时刻j位置开始出发，到最终时间点所获得的最大红包数
//两个数中的最大值
int max_2(int a, int b)
{return (a>b) ? a :b;
}
//三个数中的最大值
int maxn(int a, int b, int c)
{int max = (a>b) ? a : b;return (max>c) ? max : c;
}
// 计算最优值
// 状态转移方程为：dp[i][j]=maxn(dp[i+1][j-1]，dp[i+1][j]，dp[i+1][j+1])
void maxValue(int max_time)
{//对于每个时间所有位置从结束计算到开头//当记录了上一时刻的最大值，可以以此为参照，计算出所有位置该时刻的最大值//两重循环之后可以获取所有位置所有时刻的最大值for(int i=max_time-1; i>=0; i--){for(int j=0; j<12; j++){if(j == 0)  // 在第0位置，下一秒只能原地或向右移动 dp[i][j] = max_2(dp[i+1][j],dp[i+1][j+1]) + dp[i][j];else if(j == 11)   // 在第11位置，下一秒只能原地或向左移动 dp[i][j] = max_2(dp[i+1][j],dp[i+1][j-1]) + dp[i][j];else// 其他情况，每个时刻能够向左右或者不动dp[i][j] = maxn(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1])+ dp[i][j];}}
}
int main()
{int n;cin >> n;int location, time, value;int max_time = -1;memset(dp, 0, sizeof(dp));// 保存输入的数据到数组中 while(n--){cin >> location >> time >> value;dp[time][location] = value;if(time > max_time) max_time = time;}// 求出最大的红包maxValue(max_time);// dp[1][4]为初始时刻、初始位置对应的价值，已经从最后时刻推回来了，所以一定是最优解。cout << dp[1][4] << endl;return 0;
}

2.最大连续字段和

问题描述：略

只有两种情况：

1. 某位置最大连续子段为它本身
2. 最大连续子段长度至少为 2（至少包含它之前的一个节点）

取两者的最大值，递推方程：
$$dp[i]=max(dp[i-1]+arr[i],arr[j])$$

#include<bits/stdc++.h>
using namespace std;
int main()
{int num;cin>>num;int arr[num],dp[num]; // 读数据for(int i=0;i<num;i++){ cin>>arr[i];dp[i]=0;}// 初始化dp[0]=max(arr[0],0);for(int i=1;i<num;i++){// 状态转移方程dp[i]=max(arr[i],dp[i-1]+arr[i]); }sort(dp,dp+num);//排序cout<<dp[num-1];//输出最大值 return 0;
}

3.减肥的小k 2

题目描述

小K是个苦命的孩子，他的师傅为了多赚钱，以减肥为理由，让他去采药，并说不完成不能吃饭。野地里有许多不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。要求在规定的时间t里，采到的草药的总价值最大。

输入

第一行有2个整数T(1≤T≤1000)和M(1≤M≤100)，一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。

输出

1个整数，表示在规定的时间内可以采到的草药的最大总价值。

输入样例

70 3
71 100
69 1
1 2

输出样例

3

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005; // 最大草药数量
const int MAXT = 1005; // 最大采药时间
int t[MAXN], v[MAXN];  // t[i]是第i个草药的采摘时间，v[i]是第i个草药的价值
int dp[MAXT];          // dp[j]表示用j的时间采摘草药的最大价值
int main()
{int T, M;cin >> T >> M; // T是总时间，M是草药数量for (int i = 1; i <= M; i++){cin >> t[i] >> v[i]; // 输入每个草药的采摘时间和价值}memset(dp, 0, sizeof(dp)); // 初始化dp数组为0for (int i = 1; i <= M; i++){for (int j = T; j >= t[i]; j--){// 从后往前遍历，防止重复计算dp[j] = max(dp[j], dp[j-t[i]]+v[i]); // 状态转移方程}}cout << dp[T] << endl; // 输出用T的时间采摘草药的最大价值return 0;
}

4.最长非连续公共子序列

题目描述

略

dp [ i ] [ j ] 表示第一个串前 i 个与第二个串前 j 个组成的 lcs 子问题

状态转移方程：

如果当前指针两个字符相同：
$$dp[i][j]=dp[i-1][j-1]+1$$
如果当前指针两个字符不同：

需要从前面的两个状态恢复，两个状态分别为 dp [ i-1 ] [ j ] 和 dp [ i ] [ j-1 ] ，将它们的最大值作为该位置的状态
$$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$$

#include<bits/stdc++.h>
using namespace std;
int lcs(string s1, string s2) 
{// 初始化int m = s1.size();int n = s2.size();int dp[m+1][n+1];memset(dp, 0, sizeof(dp));// 对于a，b两个字符串，分别设定两个指针a，b// 指针分别从头开始向后移动，取两个字符串前i，j个// 这样就存在两种情况// 1.两个指针处的字符相同说明存在子串，dp[i][j] = dp[i-1][j-1] + 1 从ab指针同时退后两个的情况+1// 2.如果两个指针指向的字符不相同，说明不能从 i-1，j-1 跳转到 i，j，但是为了保存之前的结果，需要存储当前// 的最优解，当前是将两个指针同时前进1个单位，最优解一定在左指针前进一个或右指针前进一个里面选// 这就推出了最终的状态转移方程for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; 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]);}}}return dp[m][n];
}
int main() 
{string s1 = "ABCD";string s2 = "ABDE";cout << lcs(s1, s2) << endl;  // 输出 2，即 "AB" 是最长非连续公共子序列return 0;
}

5.切钢条

题目描述

一家公司购买长钢条，将其切割成短钢条出售，切割本身没有成本，长度为i的短钢条的价格为Pi。那给
定一段长度为n的钢条和一个价格表Pi,求钢条的切割方案使得收益Rn最大。

输入要求

输入钢条的长度n。

输出要求

输出获得的最大收益。

dp [ i ] 表示长度为 i 的情况下的最大利润

共有 10 种切法，所以要设置两重循环，目的是获得每个长度下的最优解，有了小长度才能以此为基础获取大长度的最优解

有两种状态，切或不切，切掉之后要考虑价值是否增加，所以产生了状态转移方程：
$$dp[i]=max(pi[j]+dp[i-j],dp[i])$$

#include<bits/stdc++.h>
using namespace std;
int pi[11] = { 0,1,5,8,9,10,17,17,20,24,30 }; //记录已知长度钢条价值
int dp[1000] = { 0 };//记录动态规划结果
int findMaxVal(int n)
{if (n == 0) // 若n为0直接返回return 0;for (int i = 1;i <= n;i++) {for (int j = 1;j <= i && j <= 10;j++) { // 第一刀最多切10种dp[i] = max(pi[j] + dp[i - j], dp[i]);//遍历所有切法}}return dp[n];
}
int main()
{int n;cin >> n;memset(dp,0,sizeof(dp));// 判断一下是否超过10，记录除数和余数int chushu = 0;int yushu = 0;int res_10 = 0;int res = 0;if(n>10){chushu = n / 10;yushu = n % 10;res_10 = findMaxVal(10);res_10 *= chushu;res = res_10 + findMaxVal(yushu);}else{res = findMaxVal(n); }cout << res << endl;return 0;
}

6.合格的盗贼

题目描述

一条街上有N个商铺；商铺i有价值V[i]的物品，你有足够的时间在晚上光顾所有的商店，人们称呼你为盗贼；每个商店都有一个报警器，会在晚上报警，但是只有相邻的2个商店同时报警时，警察才会出动；你需要证明你是个合格的盗贼。

输入要求

第一行一个整数N<=100，商店数。
第二行N个整数，每个商店的价值

输出要求

输出偷盗的最大价值。

假设在考虑第i个，只有两种个情况，只有这两种情况收益最大，按照这种思想往下推很简单就能求出最大利润

1. 第一种，i，i - 2
2. 第二种，i - 1

#include<bits/stdc++.h>
using namespace std;
int dp[101] = { 0 };
int findMaxValue(int n)
{if (n == 1)return dp[0];else if (n == 2)return max(dp[0], dp[1]);dp[1] = max(dp[0], dp[1]);for (int i = 3;i <= n;i++){// 只有两种选择，假设有 a b c 三个连续的位置// 只有两种选择不会触发警报// 1. a c// 2. b// 依据这个限制条件可以给出状态转移方程dp[i - 1] = max(dp[i - 2], dp[i - 3] + dp[i - 1]);}return dp[n - 1];
}
int main()
{int n;cin >> n;for (int i = 0;i < n;i++) {cin >> dp[i];}int res = findMaxValue(n);cout << res << endl;return 0;
}