动态规划基础练习
动态规划基础练习
有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
Input
输入数据首先包括一个整数C，表示数据的个数。
每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。Output
对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。
Sample Input
1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5Sample Output
30思路：
一个结点有两个相邻的结点，所以子问题就是以相邻结点为根，从根走向叶经过数字的最大和，
那么原来的问题既可以转化为 根上的数字加上两个子问题的最大值
那么动态转移方程就可以写出来了：acc[i][j] = num[i][j] + max(acc[i+1][j], acc[i+1][j+1])
然后记住已经算过的以节点为起点的最大和，逐步递归求解
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define MAXN 100 static int tree[MAXN][MAXN], H; static int node[MAXN][MAXN]; int acc(int i, int j) { if (i == H - 1) return tree[i][j]; else if (node[i][j] < 0) return node[i][j] = (tree[i][j] + max(acc(i+1, j), acc(i+1, j+1))); else return node[i][j]; } int main(void) { int T; scanf("%d", &T); for(int i = 0; i < T; i++) { scanf("%d", &H); memset(tree, 0, sizeof(tree)); memset(node, -1, sizeof(node)); for (int m = 0; m < H; m++) for (int n = 0; n <= m; n++) scanf("%d", &tree[m][n]); printf("%d\n", acc(0, 0)); } }B - 兑换硬币
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input
每行只有一个正整数N，N小于32768。
Output
对应每个输入，输出兑换方法数。
Sample Input
2934 12553Sample Output
718831 13137761题意很简单，就是用1,2,3的组合来表示一个数，这道题解法蛮多，我是直接用的数学方法
1,2,3的组合可以分为这么几类
- 无 3:
- 无 2
- 有 2
- 有 3:
- 仅有1个
- 仅有2个
- …
先考虑第一种没有3的情况，无2那么全都是1，肯定只有一种，有2的情况其实就是看有几对1可以组成2，自然就是 n/2 了，总的可能性就是
1+n/2再考虑第2种有3的情况，之所以这么分析有且只有几个3是因为按照题目的要求，1,2,3的组合是无序的，所以必须限制3的数量，1和2的组合很简单不需要这么细分下去。
最多有n/3个3，当限制了仅有m个3时，剩下的组合自然都是1和2的组合，那么又回到了第一种情况，这样根据3的个数算下来的结果自然是正确的
#include <bits/stdc++.h> using namespace std; int main() { int N; while(cin >> N) { long long sum = 1; // 全为１ sum += N/2; // 只考虑1 和 2 int k = N/3; for (int i = 1; i <= k; i++) { // 有i个３，考虑N - i*3中１，２的组合 int n = N - i*3; sum += 1 + n/2; } cout << sum << endl; } }- 无 3:
C - 超级跳跃
《超级跳跃》 是一款非常简单的小游戏，它的规则是这样的
a. 游戏赛道被分为了 N 块区域，每块区域具有一个价值 Ki；
b. 玩家起始站在道路的起点处，当参与者到达终点处时游戏结束；
c. 玩家每次可以选择使用超级跳跃到达前方的任意区域，但到达的区域必须满足以下两个条件之一：
① 到达的区域是终点；
② 到达的区域的价值大于当前所在的区域价值。
d. 玩家每到达一个区域，就获得这块区域的价值。
e. 不可以使用超级跳跃向身后跳。请你编写一个程序，算出对于一条《 超级跳跃》 游戏的赛道，玩家最多可以获得多少价值。
输入
输入的数据有多组， 每组数据首先是一个正整数 N (0 ≤ N ≤ 1000)， 代表赛道被分为 N 块区域，接下来是 N 个以空格为分隔符的数字 K1， K2 … KN
(−231 ≤ ���� ≤ 231 − 1)，代表 N 块区域的价值。每组数据占一行。若 N 为 0，则表示输入结束，该组数据不输出任何内容。输出
对于每组数据，在一行内输出一个正整数，表示游戏中可获得的最大价值。
样例输入
3 1 3 2
4 1 2 3 4
4 3 3 2 1
0
样例输出
4
10
3
思路:
比较简单的dp, 以起点和终点作为最开始和最后的点，设终点的值为0
状态转移方程为:
max(i) = num(i) + max{max(a), max(b), … , max(z)} (当i不是终点时需要 num(a),num(b),…, num(z) > num(i))(z < …. < b < a < i)
直接放代码:
#include <bits/stdc++.h> using namespace std; #define maxn 1005 int sum[maxn]; int d[maxn], N; int dp(int k) { if (k == 0) return 0; if (sum[k] >= 0) return sum[k]; sum[k] = 0; for (int i = k - 1; i >= 0; i--) { if (d[i] <= 0 || ((k != N + 1) && d[i] >= d[k])) continue; sum[k] = max(sum[k], dp(i)); } return sum[k] += d[k]; } int main() { while (cin >> N && N) { for (int i = 1; i <= N; i++) cin >> d[i]; d[0] = d[N + 1] = 0; memset(sum, -1, sizeof(sum)); cout << dp(N + 1) << endl; } }D：超级跳跃 Again
玩过了很久的《超级跳跃》游戏之后，虽然游戏规则没有发生变化，但你的心境发生了微妙的变化， 你想经过更多的区域，看更多的风景。
输入
输入的数据有多组， 每组数据首先是一个正整数 N (1 ≤ N ≤ 1000)， 代表赛道被分为 N 块区域，接下来是 N 个以空格为分隔符的数字 K1， K2 … KN，代表 N 块区域的价值。每组数据占一行。
输出
对于每组数据，在一行内输出一个正整数，表示最多可经过的区域数
样例输入
7
1 7 3 5 9 4 8
样例输出
4
思路：
与上一题相似，只是这题要求最长升序路
简单分析一下题目与子问题的关系后，可以得到动态转移方程：max(n) = 1 + max{max(a), max(b), max(c) …. max(z)};
需要满足 ((a, b, c, …., z < n) && num(n) > (num(a), num(b), …num(z)) )
为了方便设置节点的值为max(int),即1<<31-1, 然后递归+记忆化搜索求解即可
#include <iostream> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define maxn 1005 int num[maxn], a[maxn]; int N; int dp(int k) { if (k == 0) return 0; if (num[k] >= 0) return num[k]; num[k] = 0; for (int i = k - 1; i >= 0; i--) { if (a[i] >= a[k]) continue; num[k] = max(num[k], dp(i)); } return num[k] += 1; } int main() { while (cin >> N) { for (int i = 1; i <= N; i++) cin >> a[i]; a[N + 1] = 1 << 31 - 1; memset(num, -1, sizeof(num)); cout << dp(N + 1) - 1 << endl; } }超级跳跃 2
广受好评的《超级跳跃》游戏终于出了新作品，你作为它的粉丝已经迫不及
待的想要购买了。当你到达电玩店时，发现店前已经排起了长队，加上你一
共有 N 个人之多！每个人单独购买自己所需要的产品所需 Ki 秒，也可以选择
和排在自己前面的那个人合作，这样的话则需要 Si 秒。现在是早上 8 点， 若
这 N 个人采用了最快的方式买完了自己所需的产品， 那么买完的时候是什么
时间呢输入
输入的数据首先是一个整数 C，表示有 C 组输入数据。 每组数据首先是一个
正整数 N(1 ≤ N ≤ 10)， 然后在下一行内有 N 个整数 K1， K2 … KN， 表示 N
个人单独购买需要的时间， 接下来有 N – 1 个整数 S1， S2 … SN-1， 表示每个
人和前面那个人一起购买需要的时间。输出
对于每组数据， 在一行内输出 N 个人最快在何时全部完成购买。
输出格式为 HH:MM:SS am/pm，如开始时间就表示为 08:00:00 am，下午 2
时则表示为 14:00:00 pm。样例输入
22
20
25
40
1
8
样例输出
08:00:40 am
08:00:08 am
思路：
依然是记忆化＋dp
动态转移方程为:min(n) = max(num(n) + max(n-1), s(n-1) + max(n-2)) 不与前一个人一起 与前一个人一起第一个人只能自己买或和第二个人买
计算出需要的时间后求出具体时间打印即可
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define maxn 2005
int T, M;
int num[maxn], ss[maxn], Mem[maxn];
void PrintTime(int sec) // 根据秒数计算具体时间
{
int H, M, S, what;
S = sec % 60;
H = sec / 3600;
sec = sec % 3600;
M = sec / 60;
H += 8;
what = H >= 12 ? 1 : 0;
printf("%02d:%02d:%02d ", H, M, S);
if (what)
printf("pm\n");
else
printf("am\n");
}
int Dp(int number)
{
if (number == 0)
return num[0];
if (number == 1)
return num[1];
if (Mem[number] > 0)
return Mem[number];
return Mem[number] = min(num[number] + Dp(number - 1), ss[number - 1] + Dp(number - 2));
}
int main()
{
cin >> T;
for (int t = 0; t < T; t++)
{
cin >> M;
for (int i = 1; i <= M; i++)
cin >> num[i];
for (int i = 1; i <= M - 1; i++)
cin >> ss[i];
memset(Mem, 0, sizeof(Mem));
ss[0] = num[0] = 0;
PrintTime(Dp(M));
}
}
