当前位置：首页 > news >正文

每日一题————2026-7-12 购买奖品

news 2026/7/13 2:40:19

首先呢，先揭秘上一次的思考题答案：

2024CSP-J-T2-地图探险（explore）

#include<bits/stdc++.h>

#include <algorithm>

using namespace std;

using LL = long long;
char g[1010][1010];
bool f[1010][1010];
void solve(){
LL n, m, k, x, y, d;
scanf ("%lld %lld %lld %lld %lld %lld", &n, &m, &k, &x, &y, &d);
for (LL i = 1;i <= n;i ++) scanf ("%s", g[i] + 1);
memset(f, 0, sizeof f);
f[x][y] = 1;
while (k --){
LL nx = x, ny = y;
if (d == 0) ny ++;
else if (d == 1) nx ++;
else if (d == 2) ny --;
else nx --;
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == '.') x = nx, y = ny;
else d = (d + 1) % 4;
f[x][y] = 1;
}
LL ans = 0;
for (LL i = 1;i <= n;i ++){
for (LL j = 1;j <= m;j ++) ans += f[i][j];
}
printf ("%lld\n", ans);
}
int main(){
freopen ("explore.in", "r", stdin);
freopen ("explore.out", "w", stdout);
LL T;
cin >> T;
while (T --){
solve();
}
return 0;
}

聪明的你做出来了吗？做出来就继续加油，没做出来也没关系的，继续努力💪

好啦，开始今天的正式主题：

购买奖品

题目描述

一年一度的运动会即将开始了，科丁博士申请了一些经费，让小科去购买一些奖品用来奖励运动员们。科丁博士希望经费能够购买最大价值的奖品，小科该如何购买呢？

输入格式

第一行是两个整数N和M，分别表示希望购买的奖品的种数N以及经费金额M（N≤500，M≤6000）

接下来N行，每行3个整数，V、W、S，分别表示第i种奖品的价格、价值（价格和价值是不同的概念）以及能够购买的最大数量（购买时买0件到S件均可），其中V≤100、W≤1000、S≤10

输出格式

一行，一个数，表示此次购买奖品的最大价值（注意，不是价格！）

输入输出样例

输入样例1：

5 1000 80 20 4 40 50 9 30 50 7 40 30 6 20 20 1

输出样例1：

【耗时限制】1000ms 【内存限制】64MB

参考AC代码：

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
LL n, c, tv, tw, ts, v[5000 + 10], tot, dp[6010], w[5000 + 10];
int main(){
scanf ("%lld %lld", &n, &c);
for (LL i = 1;i <= n;i ++){
scanf ("%lld %lld %lld", &tw, &tv, &ts);
LL num = min(c / tw, ts);
for (LL j = 1;j < num;j <<= 1){
v[++ tot] = j * tv;
w[tot] = j * tw;
num -= j;
}
v[++ tot] = num * tv;
w[tot] = num * tw;
}

for (LL i = 1;i <= tot;i ++){
for (LL j = c;j >= w[i];j --){
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
printf ("%lld", dp[c]);
return 0;
}