三个都是简单题……但是第三个我死活有bug也是……
第一个 类似不同路径那个题,优先消耗小的路径,一样消耗就优先收益大的路径,我写的非常冗余,写的时候只想着赶紧调通完事……
#include <iostream> #include <vector> #include <algorithm> #include <math.h> using namespace std; void helper(vector<vector<pair<int, int>>>& grids, int& max_profit, int& min_cost) { int rows = grids.size(); if(rows == 0) return; int cols = grids[0].size(); if(cols == 0) return; vector<vector<pair<int, int>>> dp(rows, vector<pair<int, int>>(cols, make_pair(0, 0))); dp[0][0] = make_pair(grids[0][0].first, grids[0][0].second); for(int i = 1; i < rows; ++i) { dp[i][0].first += dp[i - 1][0].first + grids[i][0].first; dp[i][0].second += dp[i - 1][0].second + grids[i][0].second; } for(int i = 1; i < cols; ++i) { dp[0][i].first += dp[0][i - 1].first + grids[0][i].first; dp[0][i].second += dp[0][i - 1].second + grids[0][i].second; } for(int i = 1; i < rows; ++i) { for(int j = 1; j < cols; ++j) { if(dp[i - 1][j].first < dp[i][j - 1].first) { dp[i][j].first = dp[i - 1][j].first + grids[i][j].first; dp[i][j].second = dp[i - 1][j].second + grids[i][j].second; } else if(dp[i - 1][j].first > dp[i][j - 1].first) { dp[i][j].first = dp[i][j - 1].first + grids[i][j].first; dp[i][j].second = dp[i][j - 1].second + grids[i][j].second; } else { dp[i][j].first = dp[i - 1][j].first + grids[i][j].first; dp[i][j].second = max(dp[i - 1][j].second, dp[i][j - 1].second) + grids[i][j].second; } } } min_cost = dp[rows - 1][cols - 1].first; max_profit = dp[rows - 1][cols - 1].second; return; } int main() { int n, m; cin >> n >> m; vector<vector<pair<int, int>>> grids(n, vector<pair<int, int>>(m)); for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { cin >> grids[i][j].first; } } for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { cin >> grids[i][j].second; } } int max_profit = 0, min_cost = 0; helper(grids, max_profit, min_cost); cout << min_cost << " " << max_profit << endl; }第二个,厉害的人应该有更好的解法吧,我就是列了个表,空间换时间
#include <iostream> #include <vector> #include <algorithm> #include <math.h> using namespace std; void gettable(vector<vector<int>>& t) { for(int i = 0; i < 26; ++i) { for(int j = 1; j <= 26; ++j) { int tmp = (i + j) % 26; t[i + 'a'][j] = 'a' + tmp; } } return; } int main() { int n; cin >> n; vector<vector<int>> t(128,vector<int>(27, -1)); gettable(t); while (n--) { char c; long step = 0, time = 0; cin >> c >> step >> time; step = step % 26; if(step != 0) { time = time % (26 * step); for(int i = 0; i < time; ++i) { c = t[c][step]; } } cout << c << endl; } return 0; }
全部评论
(3) 回帖