签到题
东东在玩游戏“Game23”。
在一开始他有一个数字n，他的目标是把它转换成m，在每一步操作中，他可以将n乘以2或乘以3，他可以进行任意次操作。输出将n转换成m的操作次数，如果转换不了输出-1。
输入
输入的唯一一行包括两个整数n和m（1<=n<=m<=5*10^8).
120 51840
输出
输出从n转换到m的操作次数，否则输出-1.
7
思路
这道题是动态规划的题，我采用了记忆化的递归方法。
每个数字都是由它的二分之一的数乘二或者是三分之一的数乘三递归得到，所以递归每次到一个数字，那么就分叉成除二和除三两个方向。但是很有可能已经走过的路径之后可能又会走一遍，所以要记忆，如果开一个数组用来记忆的话，消耗空间太大了，而且元素很稀疏，浪费空间，所以我采用了哈希表来存储记忆。
代码
#include<stdio.h>
#include<unordered_map>
using namespace std;
bool now = true;
unordered_map<int, bool> sim;
int solve(int a, int b, int sum, bool is) {
if (b < a || b == 0 || !now ) return 0;
if (b == a) {
now = false;
return sum;
}
sum++;
int c = 0, d = 0;
if (b % 2 != 0);
else {
if (sim.count(b));
else c = solve(a, b >> 1, sum, now);
}
if (b % 3 != 0) d = 0;
else {
if (sim.count(c));
else d = solve(a, b / 3, sum , now);
}
sim[b] = true;
return c + d;
}
int main() {
int a, b;
scanf("%d %d", &a, &b);
if (a == b) {
printf("0");
return 0;
}
int c = solve(a, b, 0, now);
if (c == 0)
printf("-1");
else
printf("%d", c);
}
LIS & LCS
给定两个序列A和B。
求序列A的LIS和序列AB的LCS的长度。
注意，LIS为严格递增的，即a1<a2<…<ak(ai<=1,000,000,000)。
输入
第一行两个数n，m（1<=n<=5,000,1<=m<=5,000）
第二行n个数，表示序列A
第三行m个数，表示序列B
输出
输出一行数据ans1和ans2，分别代表序列A的LIS和序列AB的LCS的长度
思路
LCS我采用了LCS的构造矩阵方法，用一个矩阵来记录现在扫描到的数字和构造的上一个公共子序列的关系，照这样的话，矩阵的最右下角就是最终的LCS的答案，具体矩阵的构造方法在网上有详细的图标解释，复杂度O（）。
LIS我采用的是O（）的做法，每次扫描到数组里的一个数字，那么它的LIS就是他之前比他小的全部元素的最大LIS加上他本身。
代码
#include<iostream>
using namespace std;
int A[6000], B[6000], d[6000], L[5100][5100];
void LIS(int n) {
int max = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
int k = i - 1, sum = 0;
while (k != 0) {
if (A[k] < A[i])
sum = sum >= d[k] ? sum : d[k];
if (sum >= k) break;
k--;
}
d[i] = sum + 1;
max = max >= d[i] ? max : d[i];
}
printf("%d ", max);
}
void LCS(int n, int m) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A[i] == B[j])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = L[i - 1][j] >= L[i][j - 1] ? L[i - 1][j] : L[i][j - 1];
}
}
printf("%d", L[n][m]);
}
int main() {
int n, m; scanf("%d %d", &n, &m);
LIS(n);
for (int i = 1; i <= m; i++)
scanf("%d", &B[i]);
LCS(n, m);
}
拿数问题 II
给 n 个数，每一步能拿走一个数，比如拿第 i 个数， Ai = x，得到相应的分数 x，但拿掉这个 Ai 后，x+1 和 x-1 (如果有 Aj = x+1 或 Aj = x-1 存在) 就会变得不可拿（但是有 Aj = x 的话可以继续拿这个 x）。求最大分数。
本题和课上讲的有些许不一样，但是核心是一样，需要你自己思考。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105)，表示数字里的元素的个数
第二行包含n个整数a1, a2, ..., an (1 ≤ ai ≤ 105)
2
1 2
输出
输出一个整数：n你能得到最大分值。
2
思路
课堂上已经讨论过相关的题，我也采用差不多的思路。先对所有的元素进行排序，然后缩点，把相同的元素加起来合成一点，然后接下来就是递推公式的事了，如果本点的分数是前一个数的分数加一，那么本点的最大分数就是前前点的最大分数加上本点的分数和前一点的分数最大值其中的最大值。如果不是的话，本点的最大分数就是前一点的最大分数加上本点的分数。
代码
#include<stdio.h>
#include<algorithm>
using namespace std;
long long sim[100010];
struct edge {
long long u;//前面存元素，后面存价值
long long v;
}e[100010];
int main() {
int n; scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%lld", &sim[i]);
sort(sim, sim + n);
int k = 0;
e[0].u = sim[0];
e[0].v = sim[0];
int i = 1;
while (i < n) {
if (sim[i] == sim[i - 1]) e[k].v += sim[i];
else {
e[++k].v += sim[i];
e[k].u = sim[i];
}
i++;
}
if (k > 0) {
if (e[1].u == (e[0].u + 1)) e[1].v = max(e[0].v, e[1].v);
else e[1].v += e[0].v;
}
for (i = 2; i <= k; i++) {
if (e[i].u == (e[i - 1].u + 1)) e[i].v = max(e[i - 1].v, e[i - 2].v + e[i].v);
else e[i].v += e[i - 1].v;
}
printf("%lld", e[k].v);
}
