动态规划练习题

返回上一题
开始下一题

6. 一维消消乐
   游戏是这样的，你可以选择若干个相临的珠子，让他们同时消去。每一对珠子的消失都会使得总分数加上两颗珠子相乘的分数。注意，每个珠子只能消一次，并且珠子消去以后，还会占位。

   输入格式
   输入第一行一个整数n（1 <= n <= 10000）
   接下来一行输入n个整数wi(-1000 <= wi <= 1000)

   输出格式
   输出最大的分数

   样例输入
   8
   -9 -5 -4 -2 4 -5 -4 2

   样例输出
   73

   分析：
   我们还是考虑当前情况。
   第n个位置，我现在的选择是消去还是不消去，
   如果我选择消去，那么我需要前面一个珠子不消去,然后把前面一个珠子不消去的分数加上两者分数的乘积。
   如果我选择不消去，那么我的值就等于前一个珠子消去或者不消去的最大值。
   所以我们建立一个dp[n][2] , o表示不消去，1表示消去。

   所以转换方程为
   dp[i][0] = max(dp[i - 1][0], dp[i -1][1])
   dp[i][1] = dp[i - 1][0] + a[i] * a[i - 1]
   代码如下

   #include
   using namespace std;
   const int N = 100;
   int dp[N][2];
   int w[N];
   int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> w[i];}dp[1][1] = 0;dp[1][0] = 0;for (int i = 2; i <= n; i++){dp[i][0] = max(dp[i -1][0], dp[i - 1][1]);dp[i][1] = dp[i - 1][0] + w[i] * w[i -1];}cout << max(dp[n][0], dp[n][1]) << endl;return 0;
   }
   

返回上一题
开始下一题

7. 涂色问题
   小ai觉得白色的墙面好单调，他决定给房间的墙面涂上颜色。他买了 3 种颜料分别是红、黄、蓝，然后把房间的墙壁竖直地划分成 n 个部分，小ai希望每个相邻的部分颜色不能相同。他想知道一共有多少种给房间上色的方案。
   例如，当 n = 5时，下面就是一种合法方案。
   蓝 红 黄 红 黄

   由于墙壁是一个环形，所以下面这个方案就是不合法的。
   蓝 红 黄 红 蓝

   输入格式
   一个整数 n，表示房间被划分成多少部分。（1≤n≤50）

   输出格式
   一个整数，表示给墙壁涂色的合法方案数。

   样例输入
   4
   样例输出
   18

   分析：
   我们考虑当前位置n
   因为相邻不可以同色，我们想可不可以把第n个插入已经排好的合理解？

   经过思考，一共有两种可能。
   当n-1和1同色时，第n位置就有2种选择。因为n-1和1同色，我们就选择n-2的合理解，dp[n - 2] * 2
   当n-1和1不同色时，第n位置就只有一种选择。 dp[n - 1]
   所以我们可以构建出转换方程 将之前的两者进行相加。
   dp[n] = dp[n -1] + dp[n -2] * 2

   注意：这一题的dp值在n>30的情况下是非常大的，转换公式大于同级的斐波那契，所以需要用longlong类型。

   代码如下

   #include
   using namespace std;
   const int N = 100;
   typedef long long ll;
   ll dp[N];
   int main() {int n;cin >> n;dp[1] = 0;dp[2] = 6;for (int i = 1; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2] * 2;}cout << dp[n] << endl;
   }

返回上一题
返回目录

8. 过河
   在一个夜黑风高的晚上，有 n 个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不超过两人通过，他们只有一个手电筒，所以每次过桥后，需要有人把手电筒带回来，第 i 号小朋友过桥的时间为 a[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

   输入格式

   第一行输入一个整数 n (1 <=n <= 1000) ，表示有 n 个小朋友。

   第二行有 n 个整数 ai,ai​ 表示第 i 个小朋友过河需要的时间（0

   输出格式

   输出一个整数，表示所有小朋友过河所需要的时间
   样例输入
   4
   1 2 5 10

   样例输出
   17

   分析：
   我们考虑到你要过河，此时手电筒在对面
   因为题目说一次可以过两个人，我们思考有哪些可能？
   第一种让过河时间最少的人过来送手电筒，然后带着你一起过河。
   第二种让过河时间最少的人过来送手电筒，然后你带着n-1号一起过河，此时手电筒在对岸，接着让过河时间第二少的人过来送手电筒，带着过河时间最少的人一起过河。
   所以我们建立一个dp[i]来记录前i个人过河的最短时间。
   那么转换方程为
   dp[i] = max(dp[i - 1] + a[0] + a[i], dp[i -2] + a[0] + a[i] + 2 * a[1]);

   代码如下 :

   #include
   using namespace std;
   const int N = 100;
   int dp[N];
   int tim[N];
   int main() {int n;cin >> n;for (int i = 0; i <= n - 1; i++) {cin >> tim[i];}sort(tim, tim + n); //对过时间进行排序dp[0] = tim[0];dp[1] = tim[1];for (int i = 2; i < n; i++){dp[i] = max((dp[i - 1] + tim[0] + tim[i]), (dp[i - 2] + tim[0] + tim[i] + 2 * tim[1]));}cout << dp[n -1] << endl;return 0;
   }

4.典型框架

返回目录

1最长上升子序列(LIS)
2最长公共子序列(LCS)
3最长公共上升子序列(LCIS)
4最大子段和
5编译距离

1最长上升子序列

返回列表

Description
一个数的序列bi，当b1< b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,…,aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1<=i1　　你的任务，就是对于给定的序列，求出最长上升子序列的长度。
Input
输入的第一行是序列的长度N(1<=N<=1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
Output
最长上升子序列的长度。
Sample Input
6
1 6 2 5 4 7
Sample Output
4

#include
using namespace std;
const int N = 100;
int dp[N];
int w[N];
int main(){int n,ans = -1;cin >> n;for (int i = 1; i <= n; i++) {cin >> w[i];}dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = 1;for (int j = 1; j <= i; j++){if (w[i] > w[j]) {dp[i] = max((dp[j] + 1), dp[i]);}}ans = max(ans, dp[i]);}cout << ans << endl;return 0;
}

2最长公共子序列

返回列表

LCS是Longest Common Subsequence的缩写，即最长公共子序列。一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。
比如，对于char x[]=“aabcd”;有顺序且相互相邻的aabc是其子序列，有顺序但是不相邻的abc也是其公共子序列。即，只要得出序列中各个元素属于所给出的数列，就是子序列。
再加上char y[]=“12abcabcd”;对比出才可以得出最长公共子序列abcd。

#include
#include
using namespace std;
const int N = 100;
int dp[N][N];int main() {string s1;string s2;cin >> s1 >> s2;int len1 = int(s1.size());int len2 = int(s2.size());memset(dp, 0, sizeof(dp));for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; 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[len1][len2] <

#include
using namespace std;
const int N = 1001;
int a[N],b[N];
int dp[N][N];int main() {int n, m, maxx;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int j = 1; j <= m; j++) {cin >> b[j];}for(int i = 1; i <= n; i++) {maxx = 0;for(int j = 1; j <= m; j++) {dp[i][j] = dp[i - 1][j];if(a[i] > b[j] && maxx < dp[i - 1][j]) {maxx = dp[i - 1][j];    //维护一个前ij的最大dp值} else if (a[i] == b[j]) {dp[i][j] = maxx + 1;}}}maxx = 0;for (int i = 1; i <= m; i++) {if (maxx < dp[n][i]) maxx = dp[n][i];}cout << maxx;
}

#include
using namespace std;const int MAXN=200005;int dp[MAXN],a[MAXN],n,maxx=-100000; int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){dp[i]=max(a[i],dp[i-1]+a[i]);maxx=max(maxx,dp[i]);}printf("%d\n",maxx);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！