CF1203F2 Complete the Projects (hard version)(结论+背包+贪心)

题目

做法

对于加分的直接贪心

而掉分的用排序后的背包动规

假设有两个物品((a_1,b_1)(a_2,b_2))

选第一个物品后无法选择第二个物品，假设开始值为(r)：(r>a_1,r+b_1<a_2Longrightarrow r<a_2-b_1)

如果先选择第二个物品后可以选择第一个物品：(r>a_2,r+b_2ge a_1Longrightarrow rge a_1-b_2)

则当(a_1-b_2le a_2-b_1)时，先选择(2)更优：(a_1+b_1le a_2+b_2)

我们按照(a+b)排序后直接动规即可

细节：在处理背包时要根据(a)的限制转移

Code

#include<bits/stdc++.h>
typedef int LL;
inline LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1; c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3)+(x<<1)+c-'0'; c=getchar();
	}return x*f;
}
const LL maxn=1e2+9,inf=0x3f3f3f3f;
struct node{
	LL x,y;
}a[maxn],b[maxn];
LL n,r,ans,tot1,tot2;
LL f[60009];
inline bool cmp1(node xx,node yy){
	return xx.x<yy.x;
}
inline bool cmp2(node xx,node yy){
	if(xx.x+xx.y==yy.x+yy.y) return xx.x<yy.x;
	else return xx.x+xx.y>yy.x+yy.y;
}
int main(){
    n=Read(); r=Read();
    for(LL i=1;i<=n;++i){
    	LL x(Read()),y(Read());
    	if(y>=0) a[++tot1]=(node){x,y};
    	else b[++tot2]=(node){x,y};
	}
	std::sort(a+1,a+1+tot1,cmp1);
	for(LL i=1;i<=tot1;++i){
		if(r>=a[i].x) r+=a[i].y,++ans;
		else break;
	}
	std::sort(b+1,b+1+tot2,cmp2);
	memset(f,-inf,sizeof(f));
	f[r]=ans;
	for(LL i=1;i<=tot2;++i)
	    for(LL j=b[i].x;j<=60000;++j){	    	
		    if(j+b[i].y<0) continue;
	    	f[j+b[i].y]=std::max(f[j+b[i].y],f[j]+1);
		}
	for(LL i=0;i<=60000;++i) ans=std::max(ans,f[i]);
	printf("%d
",ans);
	return 0;
}