1 条题解

  • 2
    @ 2022-12-24 10:08:57
    #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
上传者