提交题:#69
代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node {
int w, s, v;
} a[10000005];
int dp[10000005];
bool cmp(node a,node b) {
return a.w + a.s < b.w + b.s;
}
int read() {
int x = 0,t = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
t -= 1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * t;
}
void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
signed main() {
freopen("chair.in", "r", stdin);
freopen("chair.out", "w", stdout);
int T;
T = read();
while (T --) {
memset(dp, 0, sizeof(dp));
int n, ans = 0;
n = read();
for (int i = 1;i <= n;i ++)
a[i].w = read(), a[i].s = read(), a[i].v = a[i].w;
sort(a + 1, a + n + 1, cmp);
dp[0] = 0;
for (int i = 1;i <= n;i ++) {
for (int j = a[i].s;j >= 0;j --)
dp[j + a[i].w] = max(dp[j + a[i].w], dp[j] + a[i].v);
}
for (int i = 1;i <= 10000000;i ++)
ans = max(ans, dp[i]);
write(ans);
putchar('\n');
}
return 0;
}
提示:
共 4 条回复
我已经把题删了qwq
%%%%
快读不能用longlong,好像是因为x = x * 10 + ch - '0';返回的是int?我也不清楚,反正改成signed或者去掉#define就过了
@2024-J-W010