QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #852584 | #9987. 骑行计划 | Alencryenfo | TL | 1534ms | 21584kb | C++20 | 2.5kb | 2025-01-11 13:04:57 | 2025-01-11 13:04:57 |
Judging History
answer
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
constexpr int maxn = 150;
int n, m, c, maxTime = 0;
vector<int> s;
int main() {
cin >> n >> m >> c;
s.resize(n + 1);
for (int i = 1; i <= n; i++) {
cin >> s[i];
maxTime = max(maxTime, s[i]);
}
//骑行时间的前缀和数组
vector<vector<int> > sumTime(maxTime + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= maxTime; i++) {
for (int j = 1; j <= n; j++) {
sumTime[i][j] = sumTime[i][j - 1] + (max(s[j] - i + 1,0));
}
}
//处理骑行卡
vector<vector<int> > infoCard(maxn + 1, vector<int>(n + 1,INT_MAX/2));
for (int i = 1; i <= m; i++) {
int w, d, t;
cin >> w >> d >> t;
infoCard[min(t,maxTime)][d] = min(w, infoCard[min(t,maxTime)][d]);
}
for (int i = 1; i <= maxTime; i++) {
for (int j = n - 1; j >= 1; j--) {
infoCard[i][j] = min(infoCard[i][j], infoCard[i][j + 1]);
}
}
//动态规划
vector<vector<vector<int> > > dpArray(maxTime + 1, vector<vector<int> >(n + 1, vector<int>(n + 1,INT_MAX/2)));
vector<vector<vector<int> > > dpTMPArray(maxTime + 1, vector<vector<int> >(n + 1, vector<int>(n + 1,INT_MAX/2)));
for (int i = maxTime; i >= 1; i--) {
for (int l = n; l >= 1; l--) {
for (int r = l; r <= n; r++) {
dpArray[i][l][r] = (sumTime[i][r] - sumTime[i][l - 1]) * c;
if (i==maxTime)dpTMPArray[i][l][r]=infoCard[i][r-l+1];
else dpTMPArray[i][l][r] = min(dpTMPArray[i+1][l][r],infoCard[i][r-l+1]+dpArray[i + 1][l][r]);
for (int x = l; x <= r; x++) {
for (int y = x + 1; y <= r+1; y++) {
int tmp = 0;
if (x - 1 >= l)tmp += dpArray[i][l][x - 1];
if (y <= r)tmp += dpArray[i][y][r];
dpArray[i][l][r] = min(tmp+dpTMPArray[i][x][y-1], dpArray[i][l][r]);
// for (int j = i; j <= maxTime; j++) {
// int ttmp = tmp + infoCard[j][y - x];
// if (j != maxTime) {
// ttmp += dpArray[j + 1][x][y - 1];
// }
// dpArray[i][l][r] =min( ttmp,dpArray[i][l][r]);
// }
}
}
}
}
}
cout << dpArray[1][1][n] << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 167ms
memory: 7904kb
input:
85 5408 4856 52 43 38 21 33 28 24 46 4 66 14 51 63 24 69 35 50 9 63 58 43 69 1 28 59 56 50 63 12 23 41 6 19 9 41 45 14 52 6 7 1 24 30 9 33 54 71 38 55 28 61 10 21 13 22 56 29 24 19 27 9 3 25 54 45 50 9 42 13 5 32 37 56 51 24 3 12 37 68 29 69 40 53 50 69 486593 41 10 175445 13 5 1271250 9 35 7064 1 2...
output:
1440909
result:
ok single line: '1440909'
Test #2:
score: 0
Accepted
time: 1534ms
memory: 17432kb
input:
149 1277 4355 43 52 37 18 41 38 5 57 33 37 50 51 60 31 57 64 16 15 16 51 40 65 52 71 45 24 47 74 4 64 53 37 4 73 10 35 51 49 18 21 28 2 45 29 46 50 73 17 11 66 12 6 58 56 23 67 41 64 23 71 70 72 25 7 15 58 63 58 46 51 70 65 34 65 60 17 37 2 62 53 17 74 34 18 19 3 16 21 67 43 65 64 44 14 54 71 54 65 ...
output:
2479892
result:
ok single line: '2479892'
Test #3:
score: 0
Accepted
time: 355ms
memory: 7864kb
input:
128 135 4945 20 16 3 30 17 19 18 25 7 25 1 23 18 19 29 13 13 23 30 2 25 28 7 8 19 2 31 30 22 7 7 16 26 31 15 20 3 20 29 15 26 4 23 29 19 13 7 7 24 12 11 24 8 2 5 2 18 21 25 1 5 31 22 22 23 13 19 20 23 19 10 20 14 12 23 8 18 31 14 12 25 27 5 18 27 12 5 26 22 3 13 23 16 11 29 4 22 3 9 29 26 29 13 10 2...
output:
1986485
result:
ok single line: '1986485'
Test #4:
score: 0
Accepted
time: 8ms
memory: 4304kb
input:
36 581 2377 52 79 10 73 39 70 65 43 76 81 32 54 45 45 28 56 34 35 38 16 56 78 56 39 19 4 57 11 8 31 69 53 69 73 49 58 475218 7 48 140593 4 21 6733 3 1 281348 5 27 14745 7 10 103948 6 9 21841 3 26 560211 5 71 5291 1 3 711 1 3 9948 1 15 2894 2 1 34177 1 25 187269 14 8 442896 9 22 252252 7 43 401946 13...
output:
434045
result:
ok single line: '434045'
Test #5:
score: 0
Accepted
time: 665ms
memory: 10348kb
input:
142 1462 6716 20 30 35 17 36 1 8 15 9 37 10 1 39 18 6 2 28 36 28 37 7 2 35 15 39 37 37 30 23 12 28 4 2 2 29 10 18 9 24 31 7 21 25 36 21 17 31 20 17 30 7 39 3 10 37 32 16 23 21 19 33 18 20 37 11 29 18 12 29 28 22 27 4 12 24 6 2 32 19 2 39 9 11 18 37 10 7 3 19 3 30 6 7 36 9 14 6 8 19 33 11 30 29 13 9 ...
output:
1463622
result:
ok single line: '1463622'
Test #6:
score: 0
Accepted
time: 120ms
memory: 5956kb
input:
95 7993 2085 5 24 3 23 29 10 30 3 2 29 10 22 25 25 1 15 13 10 9 32 29 29 17 21 8 27 22 26 19 6 3 28 26 5 19 11 27 13 18 23 27 30 8 6 9 2 33 18 29 4 20 27 16 7 1 11 10 21 13 8 27 6 10 3 19 25 29 33 32 4 23 14 22 6 16 8 9 19 18 2 24 24 5 13 32 33 17 27 28 24 5 31 27 24 14 90658 7 7 17303 11 1 118486 4...
output:
241704
result:
ok single line: '241704'
Test #7:
score: 0
Accepted
time: 14ms
memory: 4704kb
input:
41 6420 2466 59 27 59 46 72 65 44 29 94 40 9 27 89 68 56 92 17 86 83 14 11 65 6 37 93 36 58 79 6 13 12 54 63 58 44 25 83 74 38 18 41 83339 1 85 36883 3 31 162666 2 57 34382 6 5 303388 17 23 4074 2 1 508895 4 67 14436 2 58 7798 3 3 25055 1 15 27194 3 5 366 1 1 4453 2 3 77937 1 56 1285 1 1 116054 2 37...
output:
350353
result:
ok single line: '350353'
Test #8:
score: 0
Accepted
time: 1490ms
memory: 21584kb
input:
129 113 1675 72 64 57 113 57 94 119 127 128 89 1 82 54 107 113 69 104 125 39 2 2 119 122 45 31 122 114 40 35 46 126 47 110 39 2 6 41 22 19 16 103 47 52 59 34 83 93 45 117 119 118 6 88 71 31 43 8 107 28 12 46 92 12 120 34 53 91 39 78 85 111 4 97 20 64 5 41 42 86 40 68 43 86 38 56 87 55 15 120 107 95 ...
output:
3856152
result:
ok single line: '3856152'
Test #9:
score: -100
Time Limit Exceeded
input:
149 1294 8999 105 14 91 19 84 48 11 86 1 122 119 10 127 3 56 96 134 95 55 45 86 105 71 91 5 67 146 67 50 128 68 133 71 95 88 134 142 107 25 103 128 46 142 134 150 5 73 105 52 60 106 106 150 110 87 67 138 11 113 84 130 40 47 82 54 52 126 18 83 72 138 20 46 128 44 14 122 21 140 64 67 39 35 70 63 15 77...