这是我的代码:
#include <iostream>
#include <vector>
#include <string>
int main() {
std::string t1;
std::string t2;
int N;
std::vector<int> w(N, 0);
std::vector<int> v(N, 0);
std::vector<int> num(N, 0);
std::cin >> t1 >> t2 >> N;
for (int i = 0; i < N; ++i)
std::cin >> w[i] >> v[i] >> num[i];
if (t1.size() == 4)
t1 = "0" + t1;
if (t2.size() == 4)
t2 = "0" + t2;
int W = std::stoi(t2.substr(0, 2)) * 60 - std::stoi(t1.substr(0, 2)) * 60;
W += std::stoi(t2.substr(3, 2)) - std::stoi(t1.substr(3, 2));
std::vector<long long> dp(W, 0);
for (int i = 0; i < N; ++i) {
if (num[i] == 0) {// 完全背包
for (int j = 0; j <= W - w[i]; ++j) {
dp[j + w[i]] = std::max(dp[j + w[i]], dp[j] + v[i]);
}
}
else if (num[i] > 0) { // 多重背包
int cnt = num[i];
for (int k = 1; k <= num[i] and w[i] * k <= W; k *= 2) {
int new_w = w[i] * k;
int new_v = v[i] * k;
for (int j = W; j >= new_w; --j) {
dp[j] = std::max(dp[j], dp[j - new_w] + new_v);
}
cnt -= k;
}
if (cnt > 0) {
int new_w = w[i] * cnt;
int new_v = v[i] * cnt;
for (int j = W; j >= new_w; --j) {
dp[j] = std::max(dp[j], dp[j - new_w] + new_v);
}
}
}
}
std::cout << dp[W] << std::endl;
return 0;
}
#include #include #include
int main() { std::string t1; std::string t2; int N; std::vector w(N, 0); std::vector v(N, 0); std::vector num(N, 0); std::cin >> t1 >> t2 >> N; for (int i = 0; i < N; ++i) std::cin >> w[i] >> v[i] >> num[i]; if (t1.size() == 4) t1 = "0" + t1; if (t2.size() == 4) t2 = "0" + t2; int W = std::stoi(t2.substr(0, 2)) * 60 - std::stoi(t1.substr(0, 2)) * 60; W += std::stoi(t2.substr(3, 2)) - std::stoi(t1.substr(3, 2)); std::vector dp(W, 0); for (int i = 0; i < N; ++i) { if (num[i] == 0) {// 完全背包 for (int j = 0; j <= W - w[i]; ++j) { dp[j + w[i]] = std::max(dp[j + w[i]], dp[j] + v[i]); } } else if (num[i] > 0) { // 多重背包 int cnt = num[i]; for (int k = 1; k <= num[i] and w[i] * k <= W; k *= 2) { int new_w = w[i] * k; int new_v = v[i] * k; for (int j = W; j >= new_w; --j) { dp[j] = std::max(dp[j], dp[j - new_w] + new_v); } cnt -= k; } if (cnt > 0) { int new_w = w[i] * cnt; int new_v = v[i] * cnt; for (int j = W; j >= new_w; --j) { dp[j] = std::max(dp[j], dp[j - new_w] + new_v); } } } } std::cout << dp[W] << std::endl;
return 0;
} 报了re的问题,求问下,是string类不支持还是什么原因?我本地编译是没问题的