首页 > 分享 > 程序设计思维与实践 Week10 作业

程序设计思维与实践 Week10 作业

萌宠菠菠乐园
2024-09-26 21:01

A - 签到题

东东在玩游戏“Game23”。

在一开始他有一个数字n，他的目标是把它转换成m，在每一步操作中，他可以将n乘以2或乘以3，他可以进行任意次操作。输出将n转换成m的操作次数，如果转换不了输出-1。

Input
输入的唯一一行包括两个整数n和m（1<=n<=m<=5*10^8).

Output
输出从n转换到m的操作次数，否则输出-1.

Simple Input 1
120 51840

Simple Output 1
7

Simple Input 2
42 42

Simple Output 2
0

Simple Input 3
48 72

Simple Output 3
-1

思路：x->y需要变化的次数为 x2->y or x3->y的次数加一，简单动态规划

#include <iostream> using namespace std; int sum = -1, n, m; void func(int a, int s) {if (a == m){sum = s;return;}if (a > m) return;func(2 * a, s + 1);func(3 * a, s + 1); } int main() {cin >> n >> m;func(n, 0);cout << sum; }

123456789101112131415161718192021

B - LIS & LCS
东东有两个序列A和B。

他想要知道序列A的LIS和序列AB的LCS的长度。

注意，LIS为严格递增的，即a1<a2<…<ak(ai<=1,000,000,000)。

Input
第一行两个数n，m（1<=n<=5,000,1<=m<=5,000）
第二行n个数，表示序列A
第三行m个数，表示序列B

Output
输出一行数据ans1和ans2，分别代表序列A的LIS和序列AB的LCS的长度

Simple Input
5 5
1 3 2 5 4
2 4 3 1 5

Simple Output
3 2

LIS：对于第i个数，他可能加入到【0，i-1】序列中任意递增序列的后面，或者取代最后一个（如果他比递增序列的尾元素小，这种替换对于序列增长是有利的），因为要得到的仅仅是长度，只要记下序列的长度和尾元素即可。维护数组a2，a2[i]记录长度为i的序列的尾元素，遍历序列，找到a2[i]中第一个大于等于当前元素的，替换a2[i]。
LCS：length[i + 1][j + 1] = max(length[i][j + 1], length[i + 1][j])

#include <iostream> #include <algorithm> #define INF 0x0fffffff using namespace std; const int MAXN = 5000 + 5; int a[MAXN], a2[MAXN], b[MAXN], length[MAXN][MAXN], n, m; int LIS() {for (int i = 0; i < n; i++)*lower_bound(a2, a2 + n, a[i]) = a[i];return lower_bound(a2, a2 + n, INF) - a2; } int LCS() {for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)if (a[i] == b[j]) length[i + 1][j + 1] = length[i][j] + 1;else length[i + 1][j + 1] = max(length[i][j + 1], length[i + 1][j]);return length[n][m]; } int main() {cin >> n >> m;for (int i = 0; i < n; i++) cin >> a[i], a2[i] = INF;for (int i = 0; i < m; i++) cin >> b[i];cout << LIS() << ' ' << LCS() << 'n'; }

12345678910111213141516171819202122232425262728

C - 拿数问题 II

给一个序列，里边有 n 个数，每一步能拿走一个数，比如拿第 i 个数， Ai = x，得到相应的分数 x，但拿掉这个 Ai 后，x+1 和 x-1 (如果有 Aj = x+1 或 Aj = x-1 存在) 就会变得不可拿（但是有 Aj = x 的话可以继续拿这个 x）。求最大分数。

Input
第一行包含一个整数 n (1 ≤ n ≤ 105)，表示数字里的元素的个数

第二行包含n个整数a1, a2, …, an (1 ≤ ai ≤ 105)

Output
输出一个整数：n你能得到最大分值。

Example
Input
2
1 2
Output
2
Input
3
1 2 3
Output
4
Input
9
1 2 1 3 2 2 2 2 3
Output
10

思路：贪心，拿一个数把所有相同数字拿了

dp[i] = max(dp[i - 1], dp[i - 2] + cnt[i] * i); 1

#include <iostream> #include <algorithm> using namespace std; const int MAXN = 1e5 + 5; long longcnt[MAXN], dp[MAXN], back; int main() {int n; cin >> n;for (int i = 0; i < n; i++){int tmp; cin >> tmp;cnt[tmp]++;back = tmp > back ? tmp : back;}dp[1] = cnt[1];dp[2] = max(cnt[2] * 2, dp[1]);for (int i = 3; i <= back; i++)dp[i] = max(dp[i - 1], dp[i - 2] + cnt[i] * i);cout << dp[back];return 0; }

12345678910111213141516171819202122