这道题写的时候迷迷糊糊很困。。所以我也不知道我为什么过了QWQ
一开始思路不太好，设$f[i]$表示还剩$i$个挂钩，发现边界很难处理，但是发现物品不能一样一样按顺序枚举，需要先把挂钩$> 0$价值$ge 0$的全挂上去，然后挂钩$=0$价值$le 0$的扔掉。
只剩下两种：价值$>0$挂钩$=0$的和价值$<0$挂钩$>1$的。如果这时候现有的挂钩可以把正的价值的东西全挂上，那负的就不需要。否则考虑要加几个负价值的挂钩来挂上正价值的。
那这个就是背包。把状态$f[i]$改成用负价值的东西来增加$i$个挂钩最大价值（也就是在一堆负数里的最大值，最小花费），最后枚举再加$k$个挂钩，原来剩下$rest$个挂钩，把正价值前$rest+k$的剩余物品全挂上去。
注意一下边界，因为每个物品带的挂钩可能很大，超过一定数量直接取min。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #define dbg(x) cerr<<#x<<" = "<<x<<endl 8 #define _dbg(x,y) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl 9 using namespace std; 10 typedef long long ll; 11 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} 12 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} 13 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 14 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 15 template<typename T>inline T read(T&x){ 16 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 17 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 18 } 19 const int N=2000+6,INF=0x3f3f3f3f; 20 int c[N],val[N],f[N],w[N]; 21 int m,n,k,rest=1,thxorz,ans,pos; 22 inline int bmin(int x){return x>k?k:x;} 23 inline bool cmp(int a,int b){return a>b;} 24 25 int main(){//freopen("50.in","r",stdin);freopen("50.ans","w",stdout); 26 read(m); 27 for(register int i=1,x,y;i<=m;++i){ 28 read(x),read(y); 29 if(x<=1&&y<=0)continue; 30 else if(x>0&&y>=0)rest+=x-1,thxorz+=y; 31 else if(x==0)w[++k]=y; 32 else c[++n]=x,val[n]=y; 33 } 34 sort(w+1,w+k+1,cmp); 35 for(register int i=1;i<=k;++i)w[i]+=w[i-1]; 36 for(register int i=1;i<=k;++i)f[i]=-INF; 37 f[0]=0; 38 for(register int i=1;i<=n;++i){ 39 for(register int j=k;j>=0;--j) 40 MAX(f[bmin(j+c[i]-1)],f[j]+val[i]); 41 } 42 for(register int i=0;i<=k;++i)MAX(ans,thxorz+f[i]+w[bmin(i+rest)]); 43 printf("%d ",ans); 44 return 0; 45 }