算法强训day19

一、小易的升级之路

链接：小易的升级之路_牛客题霸_牛客网

简单题

#include<iostream>
using namespace std;
long long gcd(long long m, long long x)
{long long n ;while(x>0){n = m % x;m = x;x = n;}return m;
}
int main()
{int n;long long m;cin >> n >> m;while (n--){long long x;cin >> x;if (x <= m)m += x;elsem += gcd(m, x);}cout << m;
}

二、礼物的最大价值

链接：礼物的最大价值_牛客题霸_牛客网

动态规划

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param grid int整型vector<vector<>>* @return int整型*/int maxValue(vector<vector<int> >& grid) {int dp[202][202] = { 0 };for (int i = 1; i <= grid[0].size(); i++){dp[1][i] = dp[1][i - 1] + grid[0][i - 1];}for (int i = 1; i <= grid.size(); i++){dp[i][1] = dp[i - 1][1] + grid[i - 1][0];}for (int i = 2; i <= grid.size(); i++){for (int j = 2; j <= grid[0].size(); j++){dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];}}return dp[grid.size()][grid[0].size()];}
};

三、对称之美

直接头尾找相同字母，找不到说明没有

#include<iostream>
#include<string>
#include<stdio.h>
using namespace std;
int main()
{int n;cin >> n;while (n--){int x;cin >> x;string s[102];for (int i = 0; i < x; i++){string ss;cin >> ss;s[i] = ss;}int left = 0;int right = x - 1;while (left < right){int flag = 0;for (int i = 0; i < s[left].size(); i++){if (s[right].find(s[left][i]) != string::npos){flag = 1;break;}}if (flag == 0)break;left++;right--;}if (left >= right)cout << "Yes" << endl;elsecout << "No" << endl;}
}