Codeforces 1203F2 Complete the Projects (hard version)

[cf题面](https://codeforces.com/contest/1203/problem/F2

• Time limit
  2000 ms

• Memory limit
  262144 kB

解题思路

贪心加01背包

就像这题的那样排序，然后把涨rating的工作先尽量做了。对于掉rating的工作，可以用01背包跑，设\(dp[i][j]\)意思是处理到第\(i\)个掉分的工作，当前rating为\(j\)时能完成的最多工作的数量。然后由于按顺序处理这些工作，所以\(i\)这一维可以滚动，节省空间。

可反悔的贪心

先留坑，又可以搞成一个专题了。

源代码

贪心加01背包的——

#include
#include
int n,r;
struct Data{
	int need,delta;
	bool operator < (const Data & a)const{
		if(delta>=0)
			return needa.need;//对于掉粉的，总和越大越靠前，在输入时处理
	}
}pos[105],neg[105];//上分的和掉分的
int numpos,numneg;//两种工作的数量
int dp[60010];
int main()
{
	scanf("%d%d",&n,&r);
	for(int i=1,x,y;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		if(y>=0)
			pos[numpos++]={x,y};
		else
			neg[numneg++]={x+y,y};
	}
	std::sort(pos,pos+numpos);
	std::sort(neg,neg+numneg);
	int ans=0;
	for(int i=0;i=pos[i].need) ans++,r+=pos[i].delta;
		else break;
	}
	dp[r]=ans;//当前rating能拿到的最多的工程数量
	for(int i=0;i