XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#63481 #1290. JvJv与夏季特卖 Accepted 100 63 ms 476 K C++ / 1.3 K ining 2021-08-08 16:23:50
显示原始代码 
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
#define int long long

const int N = 1e4 + 10;
const int INF = 0x3f3f3f3f;

int a[N], b[N];  // a数组存的是原价，b数组存的是折后价
int dp[N];       // dp[i]表示的是在花费i价钱的情况下享受的最少折扣

void solve() {
    int n, L, R;
    cin >> n >> L >> R;  //变量名和题意相同
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
    memset(dp, INF, sizeof dp);  //因为题目要求的是最小值，所以应该初始化为一个极大值
    dp[0] = 0;                   //这表示的是在不花钱的时候也不享受折扣
    // dp的本质是从上一个状态转移到下一个状态，当我们全部都初始化为INF的时候，这就没有状态转移的开始了
    //所以我们会在一个能够确定的地方对数值进行初始化，让状态得以开始进行转移
    //常见的一般是什么都没有的时候为0啊，为1，左右端点等特殊情况，这个要根据题意进行设定
    for (int i = 1; i <= n; ++i)
        for (int j = R; j >= b[i]; --j) dp[j] = min(dp[j], dp[j - b[i]] + (a[i] - b[i]));
    int ans = INF;
    for (int i = L; i <= R; ++i) ans = min(ans, dp[i]);
    cout << (ans == INF ? -1 : ans) << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：8 ms
内存：420 KiB

输入文件（001.in） 

598 9527 9527
104 14
571 187
874 31
165 89
65 4
878 122
882 152
732 503
124 25
38 17
531 
<4993 bytes omitted>

答案文件（001.out） 

99

用户输出 

99

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：3 ms
内存：376 KiB

输入文件（002.in） 

372 705 1629
643 551
222 190
276 101
651 493
838 734
831 348
746 682
773 649
22 14
148 111
<3077 bytes omitted>

答案文件（002.out） 

11

用户输出 

11

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：3 ms
内存：376 KiB

输入文件（003.in） 

405 2470 2470
902 254
913 239
253 26
948 311
63 23
115 103
309 294
494 475
216 59
244 214
<3368 bytes omitted>

答案文件（003.out） 

30

用户输出 

30

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：5 ms
内存：376 KiB

输入文件（004.in） 

724 2360 4483
134 88
870 47
714 678
350 246
873 689
282 190
259 3
867 38
345 126
761 107

<6063 bytes omitted>

答案文件（004.out） 

5

用户输出 

5

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（005.in） 

88 4046 6345
277 84
660 169
800 104
763 49
432 356
145 19
227 117
67 48
388 353
77 0
421 
<653 bytes omitted>

答案文件（005.out） 

288

用户输出 

288

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：5 ms
内存：376 KiB

输入文件（006.in） 

677 5464 6403
579 331
162 134
374 326
725 542
161 17
789 246
912 639
396 40
666 277
308 25
<5680 bytes omitted>

答案文件（006.out） 

59

用户输出 

59

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（007.in） 

287 0 1927
104 62
944 28
284 238
114 15
172 55
583 549
546 217
741 176
183 82
569 299
212
<2361 bytes omitted>

答案文件（007.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：7 ms
内存：472 KiB

输入文件（008.in） 

895 6166 6900
74 66
995 245
190 148
478 267
978 18
190 21
359 206
944 917
930 897
989 897
<7530 bytes omitted>

答案文件（008.out） 

30

用户输出 

30

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（009.in） 

10 200 200
50 50
50 50
51 51
51 51
51 51
50 50
51 51
51 51
51 51
51 51

答案文件（009.out） 

-1

用户输出 

-1

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：5 ms
内存：464 KiB

输入文件（010.in） 

305 5892 8713
127 59
293 178
866 463
766 148
949 601
462 146
982 837
403 187
457 175
220 2
<2518 bytes omitted>

答案文件（010.out） 

198

用户输出 

198

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：3 ms
内存：376 KiB

输入文件（011.in） 

289 3443 6250
987 498
980 631
959 882
194 3
531 205
797 293
6 4
142 43
559 478
308 141
75
<2366 bytes omitted>

答案文件（011.out） 

63

用户输出 

63

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：6 ms
内存：476 KiB

输入文件（012.in） 

970 3243 4686
437 110
236 166
35 16
646 103
112 28
287 235
430 191
700 254
949 316
469 358
<8169 bytes omitted>

答案文件（012.out） 

32

用户输出 

32

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：3 ms
内存：376 KiB

输入文件（013.in） 

762 480 1906
532 32
911 265
223 68
930 184
829 779
124 33
738 667
76 75
680 570
94 32
369
<6380 bytes omitted>

答案文件（013.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：5 ms
内存：376 KiB

输入文件（014.in） 

543 5615 8194
538 493
688 425
457 355
253 246
455 12
558 480
414 60
565 226
231 41
199 31
<4519 bytes omitted>

答案文件（014.out） 

65

用户输出 

65

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：4 ms
内存：468 KiB

输入文件（015.in） 

241 6771 7426
51 49
523 159
162 151
702 280
433 240
314 208
554 453
233 68
191 80
142 70

<1982 bytes omitted>

答案文件（015.out） 

210

用户输出 

210

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.