1 条题解
-
2
#include<bits/stdc++.h> const int inf = 0x3f3f3f3f; using namespace std; struct ITEM{ int hk, v; }a[2010]; int sza; int b[2010], s[2010]; int szb; int n; int anssum, anscnt; int f[2010]; bool cmp1(const int A, const int B) {return A > B; } void input(){ anssum = 1; int x, y; scanf("%d", &n); for(int i = 1; i <= n; ++ i){ scanf("%d%d", &x, &y); if(x == 0){ if(y <= 0) -- i, -- n; else ++ szb, b[szb] = y; } else{ if(y >= 0) anssum += x-1, anscnt += y; else ++ sza, a[sza].hk = x-1, a[sza].v = y; } } anssum = min(anssum, n); } void ss(){ for(int i = 0; i <= 2000; ++ i)f[i] = -inf; for(int i = 0; i <= anssum; ++ i)f[i] = 0; for(int i = 1; i <= sza; ++ i) for(int j = 2000; j >= a[i].hk; -- j)f[j] = max(f[j], f[j-a[i].hk] + a[i].v); for(int i = n - 1; i >= 0; -- i)f[i] = max(f[i], f[i+1]); sort(b + 1, b + 1 + szb, cmp1); for(int i = 1; i <= 2000; ++ i)s[i] = s[i-1] + b[i]; int ans = 0; for(int i = 0; i <= 2000; ++ i){ ans = max(ans, f[i]+s[i]); } printf("%d\n", ans+anscnt); } int main(){ input(); ss(); return 0; }
信息
- ID
- 45
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 9
- 已通过
- 5
- 上传者