[cf题面](https://codeforces.com/contest/1203/problem/F2
<iframe frameborder="0" height="900px" scrolling="no" src="https://vjudge.net/problem/description/118527" style="box-sizing: inherit; height: 1755.41px;" width="100%"> </iframe>Time limit
2000 msMemory limit
262144 kB
解题思路
先留坑,吃完饭来填
源代码
#include<cstdio>
#include<algorithm>
int n,r;
struct Data{
int need,delta;
bool operator < (const Data & a)const{
if(delta>=0)
return need<a.need;
return need>a.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<numpos;i++)
{
if(r>=pos[i].need) ans++,r+=pos[i].delta;
else break;
}
dp[r]=ans;//当前rating能拿到的最多的工程数量
for(int i=0;i<numneg;i++)
{
int nd=neg[i].need-neg[i].delta,dt=neg[i].delta;//排完序之后恢复输入的原始数据
for(int j=std::max(nd,-dt);j<=r;j++)//std::max(nd,-delta)用于保证rating够用且满足要求
{//dt<0,j+dt是更小的rating,比较的作用是降到那个rating时可以完成的最多的工作数量
dp[j+dt]=std::max(dp[j]+1,dp[j+dt]);
}
}
ans=-1;
for(int i=0;i<=r;i++)
{
ans=std::max(dp[i],ans);
}
printf("%d\n",ans);
return 0;
}