4247: 挂饰
题目：传送门
题解：
看完题目很明显的一道二维背包（一开始还推错了）
设f[i][j]表示前i个挂饰选完（可以有不选）之后还剩下j个挂钩的最大值（j最多贡献为n）
那么f[i][j]=max(f[i-1][j],f[i-1][max(j-a[i].w,0)+1]+a[i].x);（一开始忘了加1真的是沙茶）
然后就直接乱打一通...然后又错了
再想想，如果前面的好几个物品都没有挂钩...那我怎么转移，所以排序一下挂钩数目咯
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
struct node
{
int w,x;
}a[];
int n,f[][];//前i个物品剩j个挂钩
bool cmp(node n1,node n2){return n1.w>n2.w;}
int main()
{
scanf("%d",&n);for(int i=;i<=n;i++)scanf("%d%d",&a[i].w,&a[i].x);
sort(a+,a+n+,cmp);
for(int i=;i<=n;i++)for(int j=;j<=n+;j++)f[i][j]=-;f[][]=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
f[i][j]=max(f[i-][j],f[i-][max(j-a[i].w,)+]+a[i].x);
int ans=-;for(int i=;i<=n;i++)ans=max(ans,f[n][i]);
printf("%d\n",ans);
return ;
}