A：签到题

题目：

东东在玩游戏“Game23”。

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

输入：

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

输出：

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

样例：

样例1：

输入：

120 51840

输出：

样例2：

输入：

42 42

输出：

样例3：

输入：

48 72

输出：

-1

思路：

递归实现，深度优先的策略就够了orz（广度优先应该也可）

#include<iostream>
using namespace std;
bool yes=0;
int number=0;
void zhuanhua(int n,int m,int times)
{
    if(n==m) 
    {
        yes=1;number=times;
        return;
    }
    if(n>m) return;
    zhuanhua(n*2,m,times+1);
    zhuanhua(n*3,m,times+1);
}
int main()
{
    int n,m;cin>>n>>m;
    zhuanhua(n,m,0);
    if(!yes) cout<<"-1"<<endl;
    else cout<<number<<endl;
    return 0;
 }

B：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的长度

样例：

输入：

5 5
1 3 2 5 4
2 4 3 1 5

输出：

思路：

dp的问题！
LIS：
（参考）https://blog.csdn.net/qq_41765114/article/details/88415541
这里面讲解的非常直观。比较简单，更新一个数据时就是找他前面比他小的数，然后更新。
LCS :
设计状态：假设 f[i][j] 为 A1, A2, …, Ai 和 B1, B2, …, Bj 的 LCS 长度
初始化：初始 f[1][0] = f[0][1] = f[0][0] = 0
转移方程：
if Ai == Bj
f[i][j] = f[i-1][j-1] + 1
否则
f[i][j] = max(f[i-1][j], f[i][j-1])
答案：f[n][m]

#include<iostream>
#include<string>
#include<string.h>
#include<cstring>
using namespace std;
int max(int a,int b)
{
    if(a>b) return a;
    else return b;
}
//LIS 最长递增子序列 
//LCS 最长公共子序列
long long a[5050];
long long b[5050];
int dp[5050]; 
int dpp[5050][5050];
int main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],dp[i]=1;
    int final1=1;
    int final2=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])
            {
                dp[i]=max(dp[j]+1,dp[i]);
            }
        }
        final1=max(final1,dp[i]);
    }
    cout<<final1<<" ";
    for(int i=1;i<=m;i++) cin>>b[i];
    
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(a[i]==b[j]) dpp[i][j]=dpp[i-1][j-1]+1;
            else dpp[i][j]=max(dpp[i-1][j],dpp[i][j-1]);
        }
    }
    cout<<dpp[n][m]<<endl;
    return 0;
}

C：拿数问题II

题目：

YJQ 上完第10周的程序设计思维与实践后，想到一个绝妙的主意，他对拿数问题做了一点小修改，使得这道题变成了拿数问题 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)

输出：

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

样例：

输入：

9
1 2 1 3 2 2 2 2 3

输出：

思路：

当取了i 位置 x 这个数，数值为x-1和x+1的数都不能取
其实这和上课讲的题是关联巨大的。
首先初始化。之后考虑状态转移。既然原来的这时候就只需要得到输入数据的最小值和最大值，确定范围，状态转移方程和上课讲的就相同
状态转移：
dp[i]=max(dp[i-1],dp[i-2]+i*sum[i]); 方程中的i 就是数值。

需要注意的是方程中均有i-2，因此初始化前两个数，

#include<iostream>
using namespace std;
int a[100010];
struct number
{
    long long zhi;
    long long muber;
};
long long max(long long a,long long b)
{
    if(a>b) return a;
    else return b;
}
number s[100010];
long long dp[100010];
int main()
{
    int m;cin>>m;
    long long k;int ds=0;
    for(int i=1;i<=m;i++)
    {
        cin>>k;
        int ok=0;
        for(int j=0;j<ds;j++)   
        {
            if(s[j].zhi==k)
            {
                s[j].muber++;
                ok=1;
                break;
             } 
        }
        if(!ok) s[ds].zhi=k,s[ds].muber=1,ds++;
    } 
/*  for(int i=0;i<ds;i++)
    {
        dp[i]=s[i].muber*s[i].zhi;
    }*/
    dp[0]=s[0].muber*s[0].zhi;
    dp[1]=s[1].muber*s[1].zhi;
    for(int i=2;i<ds;i++)
    {
        dp[i]=max(dp[i-1],dp[i-2]+s[i].muber*s[i].zhi);
    }
    cout<<dp[ds-1]<<endl;
    return 0;
}

十周作业