没啥好说，都是一遍过
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; }
