腾讯算法笔试 第5题

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() {     int n;     cin >> n;     vector<int> work(n, 0);     vector<int> play(n, 0);     int dp1, dp2, lp1, lp2;     dp1 = dp2 = lp1 = lp2 = 0;     for (int i = 0; i < n; i++)         cin >> work[i];     for (int i = 0; i < n; i++)         cin >> play[i];     for (int i = 0; i < n; i++)     {         lp1 = dp1;         lp2 = dp2;         if (work[i] == 0 && play[i] == 0)         {             dp2 = dp1 = max(lp1, lp2);         }         else if (work[i] == 1 && play[i] == 1)         {             dp1 = max(lp1, lp2 + 1);             dp2 = max(lp2, lp1 + 1);         }         else if (work[i] == 1)         {             dp2 = max(lp1, lp2);             dp1 = max(lp1, lp2 + 1);         }         else         {             dp1 = max(lp1, lp2);             dp2 = max(lp2, lp1 + 1);         }     }     cout << n - max(dp1, dp2) << endl;     system("pause");     return 0; } AC

#include <iostream> #include <vector> using namespace std; int main() { int n; cin>>n; vector<int> com(n); vector<int> train(n); vector<int> dppp(n); for(int i = 0;i < n;i++) cin>>com[i]; for(int i = 0;i < n;i++) cin>>train[i]; //0:表示工作，1：锻炼 ， 2：休息 int num = 0; for(int i = 0;i < n;i++) { if(i == 0 || dppp[i-1] == 2) //随便选 , 只跟后面有关 { if(com[i] == 0 && train[i] == 0) { dppp[i] = 2 ; num++; }else if(com[i] == 1 && train[i] == 1) //两个都可以选 { if(i+1 < n) { if(com[i+1] == 1 && train[i+1] == 1 || (com[i+1] == 0 && train[i+1] == 0)) { dppp[i] = 2; } else { if(com[i+1] == 1) dppp[i] = 1; else dppp[i] = 0; } } else { } }else { if(com[i] == 1) dppp[i] = 0; else dppp[i] = 1; } }else { if(dppp[i-1] == 0) //前一天工作 { if(train[i] == 1) { dppp[i] = 1; }else { dppp[i] = 2; num++; } }else if(dppp[i-1] == 1) //前一天锻炼 { if(com[i] == 1) { dppp[i] = 0; }else { dppp[i] = 2; num++; } } } //cout<<i<<"  "<<dp[i]<<endl; }/* for(int i = 0;i < n;i++) cout<<dp[i]<<"   ";*/ cout<<num<<endl; return 0; } 瞎写的，然后过了

import sys def get_score(n, nums): dp = [[0] * 3 for _ in range(n)] dp[0] = nums[0] state = [1] * 3 for i in range(3): if nums[0][i] == 0: state[i] == -1 for i in range(1, n): state1 = state[:] for j in range(3): # print(dp, state, nums[i]) cur_max = dp[i - 1][1] cur_idx = 1 for k in [-1, 0, 1]: last_idx = j + k if last_idx < 0 or last_idx > 2: continue cur_sum = dp[i - 1][last_idx] + state[last_idx] * nums[i][j] if cur_sum > cur_max: cur_max = cur_sum cur_idx = last_idx dp[i][j] = cur_max state1[j] = state[cur_idx] if nums[i][j] == 0: state1[j] *= -1 state = state1 return max(dp[-1]) if __name__ == "__main__": n = int(sys.stdin.readline().strip()) nums = [] for _ in range(n): nums.append(list(map(int, sys.stdin.readline().strip().split()))) print(get_score(n, nums)) 交卷了才调完，没测哈～

算法都通过多少啊