P1833 樱花（有疑惑）
最逆天的一集
一开始打算用最初的二维数组dp做，一直80tps，T一个点，WA一个点。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
string a, b;
int T, N;
int t[10010], c[10010], p[10010];
int dp[10010][1010];
void getTime() {
int ha = 0, hb = 0, ma = 0, mb = 0;
bool is_ha = true, is_hb = true;
cin >> a >> b;
for (int i = 0; i < a.length(); i++) {
if (a[i] != ':' && is_ha) {
ha = ha * 10 + a[i] - '0';
continue;
}
is_ha = false;
if (a[i] != ':' && !is_ha) {
ma = ma * 10 + a[i] - '0';
}
}
for (int i = 0; i < b.length(); i++) {
if (b[i] != ':' && is_hb) {
hb = hb * 10 + b[i] - '0';
continue;
}
is_hb = false;
if (b[i] != ':' && !is_hb) {
mb = mb * 10 + b[i] - '0';
}
}
if (mb < ma) {
T = mb + 60 - ma + (hb - ha - 1) * 60;
} else {
T = mb - ma + (hb - ha) * 60;
}
}
int main() {
getTime();
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> t[i] >> c[i] >> p[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= T; j++) {
if (p[i] != 0) {
for (int k = 1; k * t[i] <= T && k <= p[i]; k++) {
if (k * t[i] <= j)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * t[i]] + k * c[i]);
else
dp[i][j] = dp[i - 1][j];
}
} else {
for (int k = 0; k * t[i] <= j; k++) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * t[i]] + k * c[i]);
}
}
}
}
cout << dp[N][T];
return 0;
}
改不出来一点，第二天早上起来索性直接把第一维删掉，改成优化版dp，然后就ac了？？
不明白为什么
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
string a, b;
int T, N;
int t[10010], c[10010], p[10010];
int dp[1010];
void getTime() {
int ha = 0, hb = 0, ma = 0, mb = 0;
bool is_ha = true, is_hb = true;
cin >> a >> b;
for (int i = 0; i < a.length(); i++) {
if (a[i] != ':' && is_ha) {
ha = ha * 10 + a[i] - '0';
continue;
}
is_ha = false;
if (a[i] != ':' && !is_ha) {
ma = ma * 10 + a[i] - '0';
}
}
for (int i = 0; i < b.length(); i++) {
if (b[i] != ':' && is_hb) {
hb = hb * 10 + b[i] - '0';
continue;
}
is_hb = false;
if (b[i] != ':' && !is_hb) {
mb = mb * 10 + b[i] - '0';
}
}
if (mb < ma) {
T = mb + 60 - ma + (hb - ha - 1) * 60;
} else {
T = mb - ma + (hb - ha) * 60;
}
}
int main() {
getTime();
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> t[i] >> c[i] >> p[i];
}
for (int i = 1; i <= N; i++) {
for (int j = T; j >= 1; j--) {
if (p[i] != 0) {
for (int k = 1; k * t[i] <= T && k <= p[i]; k++) {
if (k * t[i] <= j)
dp[j] = max(dp[j], dp[j - k * t[i]] + k * c[i]);
}
} else {
for (int k = 0; k * t[i] <= j; k++) {
dp[j] = max(dp[j], dp[j - k * t[i]] + k * c[i]);
}
}
}
}
cout << dp[T];
return 0;
}