没啥好说，都是一遍过
1.求最小公倍数
思路：
求lcm。其实就是两数之乘积除以两个数的gcd。gcd就是是求两个数的最大公约数。
代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int a, b;
cin >> a >> b;
cout << (long long)a * b / gcd(a, b) << endl;
return 0;
}
2.数组中的最长连续子序列
思路：
题目描述有问题，求的答案跟子序列没半毛钱关系。转换一下题意就是，从一堆数里面选出n个数，这n个数排序后是一个严格+1的递增序列。既然和顺序无关，那就可以先sort.。sort完后用双指针维护一个严格+1的递增区间 。考虑到有重复数字的问题，在此之前去重就好了。
这题其实也可以用dp去做，dp[i]表示以i结尾的最长序列有多长，于是dp[i]=max (dp[i-1]+1 ,dp[i])
这里的dp可以用map维护。
代码：
#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
int MLS(vector<int>& arr) {
if (arr.size() == 1)return 1;
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());
int ans = 0;
int i = 1, j = 0;
int n = arr.size();
for (; i < n; i++) {
if (arr[i] - arr[i - 1] != 1) {
ans = max(ans, i - j);
j = i;
}
}
if (arr[n - 1] - arr[n - 2] == 1) {
ans = max(ans, i - j);
}
return ans;
}
};3.字母收集
思路：
跟杨辉三角没区别。
一般这种dp都是反过来思考的。对于一个（i,j）来说，到达这个点最多有多少分？怎么到达这个点？也就是这个点的上一个状态有哪几种？ 只能是dp[i-1][j](表示上面)和dp[i][j-1](左边)来的。所以dp[i][j]就等于这两个状态的最大值。于是轻而易举得到状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i][j-1])+val（arr[i]][j]）。注意val表示（i，j）这个点的分数。
简单来说一下对于这种路径dp的思路吧：
假设某种路径问题是，从那里到那里的最大分数啊这种问题。
优先考虑对于当前状态，上一个状态有哪些？
就比如上一道题用dp怎么去想呢？从前往后，到达i这个点的状态有哪些？只能是i-1，所以dp[i]=dp[i-1]+1.
线性dp,区间dp，树上dp基本上都是这么想的。当然具体题目具体的来。
代码：
#include <iostream>
using namespace std;
const int N=510;
char g[N][N];
int f[N][N];
int main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int k=0;
if(g[i][j]=='l')k=4;
else if(g[i][j]=='o')k=3;
else if(g[i][j]=='v')k=2;
else if(g[i][j]=='e')k=1;
f[i][j]=max(f[i-1][j]+k,f[i][j-1]+k);
}
}
cout<<f[n][m]<<endl;
return 0;
}
