[JOISC2014]ストラップ

题目大意：

有\(n(n\le2000)\)个挂饰，每个挂饰有一个喜悦值\(b_i(|b_i|\le10^6)\)，下面有\(b_i(b_i\le10^6)\)个挂钩，可以用来挂别的挂饰。一开始只有一个挂钩，问喜悦值总和的最大值。

思路：

\(f[i][j]\)表示考虑前\(i\)个挂饰，还多\(j\)个钩子时，喜悦值总和的最大值。

考虑同样的一堆挂件，先挂\(a_i\)大的可以尽可能避免钩子不够用的情况。因此需要先将所有挂件按\(a_i\)从大到小排序。

时间复杂度\(\mathcal O(n^2)\)。

源代码：

#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
#include<functional>
inline int getint() {
register char ch;
register bool neg=false;
while(!isdigit(ch=getchar())) neg|=ch=='-';
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return neg?-x:x;
}
const int N=2001;
struct Node {
int a,b;
bool operator > (const Node &rhs) const {
return a>rhs.a;
}
};
Node p[N];
int f[N][N];
inline void upd(int &a,const int &b) {
a=std::max(a,b);
}
int main() {
const int n=getint();
for(register int i=1;i<=n;i++) {
p[i].a=getint();
p[i].b=getint();
}
std::sort(&p[1],&p[n]+1,std::greater<Node>());
std::fill(&f[0][0],&f[0][n]+1,INT_MIN);
f[0][1]=0;
for(register int i=1;i<=n;i++) {
std::copy(&f[i-1][0],&f[i-1][n]+1,f[i]);
for(register int j=1;j<=n;j++) {
if(f[i-1][j]==INT_MIN) continue;
upd(f[i][std::min(j-1+p[i].a,n)],f[i-1][j]+p[i].b);
}
}
int ans=0;
for(register int i=0;i<=n;i++) {
upd(ans,f[n][i]);
}
printf("%d\n",ans);
return 0;
}