9.3美团笔试

第四题，仅供参考：89通过率 #include<iostream> (30316)#include<vector> #include<string> (30191)#include<sstream> #include<unordered_map> (30194)#include<unordered_set> #include<queue> //(31144)#include <math.h> #include <stdio.h> //(31145)#include<cstdlib> #include<string.h> (31146)#include<limits.h> #include<set> (30954)#include<thread> #include<stack> (31147)#include <numeric> #include<algorithm> // system("chcp 65001"); //中文用 using namespace std; //第四题, Viterbi算法 int main() { int n, m, k; scanf("%d %d %d", &n, &m, &k); vector<int> C(m, 0), A(m, 0), B(m, 0); for (int i = 0; i < m; ++i) { // 任务所在地点 scanf("%d", &C[i]); } for (int i = 0; i < m; ++i) { // 同地点的收益 scanf("%d", &A[i]); } for (int i = 0; i < m; ++i) { // 不同地点的收益 scanf("%d", &B[i]); } vector<vector<vector<int>>> dp(m, vector<vector<int>>(2, {0,0})); dp[0][0] = { 0, k }; // 不去做这个任务 if (k == C[0]) { dp[0][1] = {A[0], C[0]}; } else { dp[0][1] = { B[0], C[0] }; } for (int i = 1; i < m; ++i) { // 状态转移: // dp[i][0] = max(dp[i-1][0][0], do[i-1][0][1]) 这一天什么都不做，相等怎么办? if (dp[i - 1][0][0] > dp[i - 1][1][0]) { dp[i][0] = dp[i - 1][0]; } else { dp[i][0] = dp[i - 1][1]; } int val1; if (dp[i - 1][1][1] == C[i]) { val1 = A[i] + dp[i - 1][1][0]; } else { val1 = B[i] + dp[i - 1][1][0]; } int val2; if (dp[i - 1][0][1] == C[i]) { val2 = A[i] + dp[i - 1][0][0]; } else { val2 = B[i] + dp[i - 1][0][0]; } if (val1 > val2) { dp[i][1] = { val1, C[i] }; } else { dp[i][1] = { val2, C[i] }; } } printf("%d", max(dp[m - 1][1][0], dp[m - 1][0][0])); return 0; }