[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;

}