动态规划基础题(第2题)：累积和问题，华丽丽超时
碎碎念
- 看似越简单问题里面越有陷阱，本题最初的题解华丽丽的有4个case超时。
- AtCode比赛二选一机制实在太不友好了，我之前学了一堆的偷分大法一点都用不上；
- 你永远不要相信C级的题可以用暴力解完成，如果你这么做了，恭喜你将收获至少N个TLE或者N个WA还有一个大鸭蛋。
标签
- 动态规划、累积和
合集
- 【动态规划】累积和
题目地址
010 - Score Sum Queries
- https://atcoder.jp/contests/typical90/tasks/typical90_j
问题描述
入力
入力は以下の形式で標準入力から与えられます。
N
C1 P1
C2 P2
⋮
CN PN
Q
L1 R1
L2 R2
⋮
LQ RQ
出力
A1 B1
A2 B2
⋮
AQ BQ
入力例 1
7
1 72
2 78
2 94
1 23
2 89
1 40
1 75
1
2 6
出力例 1
63 261
学籍番号 2 \sim 6 番の 1 組生徒における、期末試験合計点は 23+40=63 です。また、学籍番号 2 \sim 6 番の 2 組生徒における、期末試験合計点は 78+94+89=261 です。
入力例 2
7
1 72
2 78
2 94
1 23
2 89
1 40
1 75
10
1 3
2 4
3 5
4 6
5 7
1 5
2 6
3 7
1 6
2 7
出力例 2
72 172
23 172
23 183
63 89
115 89
95 261
63 261
138 183
135 261
138 261
入力例 3
1
1 100
3
1 1
1 1
1 1
出力例 3
100 0
100 0
100 0
一方の組の生徒が存在しないケースもあります。
入力例 4
20
2 90
1 67
2 9
2 17
2 85
2 43
2 11
1 32
2 16
1 19
2 65
1 14
1 51
2 94
1 4
1 55
2 90
1 89
1 35
2 81
20
3 17
5 5
11 11
8 10
3 13
2 6
3 7
3 5
12 18
4 8
3 16
6 8
3 20
1 12
1 6
5 16
3 10
17 19
4 4
7 15
出力例 4
175 430
0 85
0 65
51 16
116 246
67 154
0 165
0 111
213 184
32 156
175 340
32 54
299 511
132 336
67 244
175 314
51 181
124 90
0 17
120 186
题解
小码匠
- 很暴力，很超时，华丽丽掉进陷阱
- 时间复杂度：O * N
void coder_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<pair<int, long long >> c_p(n);
for (int i = 0; i < n; i++) {
cin >> c_p[i].first >> c_p[i].second;
}
int q;
cin >> q;
int temp, temp_2;
long long dp_1 = 0;
long long dp_2 = 0;
for (int i = 0; i < q; i++) {
cin >> temp >> temp_2;
for (int j = temp - 1; j < temp_2; j++) {
if (c_p[j].first == 1) {
dp_1 += c_p[j].second;
} else {
dp_2 += c_p[j].second;
}
}
cout << dp_1 << " " << dp_2 << endl;
dp_1 = 0;
dp_2 = 0;
}
}
小码匠二次题解
- AC
- 时间复杂度：O+N
void best_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<long long> one(n + 1);
vector<long long> tow(n + 1);
one[0] = 0;
tow[0] = 0;
long long C, P;
for(int i = 1; i <= n; i++) {
cin >> C >> P;
if(C == 1) {
one[i] = one[i - 1] + P;
tow[i] = tow[i - 1];
} else {
tow[i] = tow[i - 1] + P;
one[i] = one[i - 1];
}
}
int q;
cin >> q;
int L, R;
for(int i = 0; i < q; i++) {
cin >> L >> R;
cout << one[R] - one[L - 1] << " " << tow[R] - tow[L - 1] << endl;
}
}
待补知识点
- 继续学习累积和
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-05-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号