A：签到题
题目：
东东在玩游戏“Game23”。
在一开始他有一个数字n，他的目标是把它转换成m，在每一步操作中，他可以将n乘以2或乘以3，他可以进行任意次操作。输出将n转换成m的操作次数，如果转换不了输出-1。
输入：
输入的唯一一行包括两个整数n和m（1<=n<=m<=5*10^8).
输出：
输出从n转换到m的操作次数，否则输出-1.
样例：
样例1：
输入：
120 51840
输出：
7
样例2：
输入：
42 42
输出：
0
样例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
输出：
32
思路：
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
输出：
10
思路：
当取了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;
}
网友评论