0826jd笔试后端方向

第一题忘记了....

第二题是简单模拟+分类讨论

第三题是经典背包问题，dp[i][j] = max(dp[i-1][j],暴力分数+dp[i-1][j-暴力用时],正解分数+dp[i-1][j-正解用时])，代码在这

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n, t; cin >> n >> t;

vector<vector<pair<int, int>>> data(n, vector<pair<int, int>>());// 0 正 1 暴

for (int i = 0; i < n; i++) {

pair<int, int> p1, p2;

cin >> p1.first >> p1.second >> p2.first >> p2.second;

data[i].emplace_back(p1);

data[i].emplace_back(p2);

}

vector<vector<int>> dp(n, vector<int>(t + 1, 0));//dp[i][j] :i题j时间，表示最大得分

vector<vector<int>> zhuangtai(n, vector<int>(t + 1, 0));//0 不做 1 正 2 暴

for (int i = 0; i < n; i++) {

for (int j = 0; j <= t; j++) {

if (i == 0) {

if (j < data[i][1].first) {

dp[i][j] = 0;

zhuangtai[i][j] = 0;

}

else if (j >= data[i][1].first && j < data[i][0].first) {

dp[i][j] = data[i][1].second;

zhuangtai[i][j] = 2;

}

else {

dp[i][j] = data[i][0].second;

zhuangtai[i][j] = 1;

}

}

else {

int baoscore = data[i][1].second, zhengscore = data[i][0].second;

int baotime = data[i][1].first, zhengtime = data[i][0].first;

if (j < baotime) {

dp[i][j] = dp[i - 1][j];

zhuangtai[i][j] = 0;

}

else if (j >= baotime && j < zhengtime) {

if (dp[i - 1][j] >= baoscore + dp[i - 1][j - baotime]) {

dp[i][j] = dp[i - 1][j];

zhuangtai[i][j] = 0;

}

else {

dp[i][j] = baoscore + dp[i - 1][j - baotime];

zhuangtai[i][j] = 2;

}

}

else {

if (dp[i - 1][j] >= baoscore + dp[i - 1][j - baotime] && dp[i - 1][j] >= zhengscore + dp[i - 1][j - zhengtime]) {

dp[i][j] = dp[i - 1][j];

zhuangtai[i][j] = 0;

}

else if (baoscore + dp[i - 1][j - baotime] >= dp[i - 1][j] && baoscore + dp[i - 1][j - baotime] >= zhengscore + dp[i - 1][j - zhengtime]) {

dp[i][j] = baoscore + dp[i - 1][j - baotime];

zhuangtai[i][j] = 2;

}

else {

dp[i][j] = zhengscore + dp[i - 1][j - zhengtime];

zhuangtai[i][j] = 1;

}

}

}

}

}

vector<char> result(n, 'F');

int reversetime = t;

for (int i = n - 1; i >= 0; i--) {

int usetime;

//0 不做 1 正 2 暴

if (zhuangtai[i][reversetime] == 0) {

usetime = 0;

result[i] = 'F';

}

if (zhuangtai[i][reversetime] == 1) {

usetime = data[i][0].first;

result[i] = 'A';

}

if (zhuangtai[i][reversetime] == 2) {

usetime = data[i][1].first;

result[i] = 'B';

}

reversetime = reversetime - usetime;

}

for (int i = 0; i < n; i++) {

cout << result[i];

}

return 0;

}

// 64 位输出请用 printf("%lld")