目录

1.最小公倍数

2.最长连续的子序列

3.字母收集

---

1.最小公倍数

求最小公倍数_牛客题霸_牛客网

算法思路：

这就是一道数学题，a,b的最小公倍数 = a * b / 最大公约数。

使用辗转相除法，求a，b的最大公约数。

#include <iostream>
using namespace std;int gcb(int a, int b) //求最大公约数
{if(b == 0) return a;return gcb(b , a % b);
}int main() 
{int a, b;cin >> a >> b;cout << a * b / gcb(a,b) << endl;return 0;
}

2.最长连续的子序列

数组中的最长连续子序列_牛客题霸_牛客网

 算法思路：

将数组排序，双指针遍历数组求最长即可

class Solution {
public:int MLS(vector<int>& arr) {sort(arr.begin(), arr.end());int count = 0;int ret = 0;for(int i = 1; i < arr.size(); i++){if(arr[i] - arr[i-1] == 1)// 说明是连续的{count++;}else if(arr[i] - arr[i-1] == 0)// 相等的{continue;}else //不连续{ret = max(ret, count);//更新最大值 count = 0;}}ret = max(ret, count);//特殊处理 1 2 3 4 5 6这种情况return ret + 1;}
};

3.字母收集

字母收集_牛客题霸_牛客网

算法思路：

这是一道动态规划、

1.状态表示：dp[i][j] 表示到达i，j位置的最大分数。

2.状态转移方程：直接分析最后一步，想到达dp[i][j]我只有两种情况，第一种从dp[i-1][j]到达，第二种是从dp[i][j-1]到达，dp[i][j]只需要取这两种情况的最大值 + i，j位置的分数。

处理一些细节问题，dp[i][j] = max(dp[i-1][j], dp[i][j-1]); + sorc， i和j是数组的边界怎么办？？

输入的时候就从 i = 1 开始输出，就想到与空出最外层的一圈0.

#include <iostream>
using namespace std;const int N = 510;
char g[N][N];
int dp[N][N];int n, m;
int main() 
{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 soce = 0;if(g[i][j] == 'l') soce = 4;else if (g[i][j] == 'o') soce = 3;else if (g[i][j] == 'v') soce = 2;else if (g[i][j] == 'e') soce = 1;dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + soce;}}cout << dp[m][n] << endl;return 0;
}
// 64 位输出请用 printf("%lld")