Gym 101081K
题意：n 个箱子，自重为wi，承重 ri(包括本身)，问最多可以有多少个箱子堆在一起。
tags：
dp[i][j]表示前 i 个箱子取 j 个堆在一起的最小重量，但这里要先按 ri 从小到大排个序。
可以这样理解，设两个箱子p1,p2，参数为w1, r1, w2, r2，且 r1<r2。 如果 p2 能放在 p1 上面，则 p1 肯定也能放在 p2 上，而且后者是更优的，因为会有更多的剩余承重。
所以排了序后，对于第 i 个，只要考虑它前面的箱子即可。
然后 dp 转移：
1】如果不取第 i 个，则 dp[i][j] = min(dp[i][j], dp[i-1][j] );
2】如果能取第 i 个，则 dp[i][j] = min(dp[i][j], dp[i-1][j-1]+w[i] );
dp[i][0]初始化为 0，其它为 INF，即前 i 个取 j 个无法承重则为无穷大。
最后在 dp[n][i] 中取不为 INF 的最大的 i 即是答案。
#includeusing namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi first#define se secondtypedef long long ll;const int N = 1005;int T, n, dp[N][N];struct P { int wi, ri; bool friend operator < (P a, P b) { return a.ri < b.ri; }} p[N];int main(){ scanf("%d", &T); while(T--) { mes(dp, INF); scanf("%d", &n); rep(i,1,n) scanf("%d%d", &p[i].wi, &p[i].ri); sort(p+1, p+1+n); rep(i,0,n) dp[i][0] = 0; rep(i,1,n) { rep(j,1,i) { if(i-1 >= j) dp[i][j] = min(dp[i][j], dp[i-1][j]); if(dp[i-1][j-1]+p[i].wi<=p[i].ri && dp[i][j]>dp[i-1][j-1]+p[i].wi) dp[i][j] = dp[i-1][j-1]+p[i].wi; } } per(i,n,1) if(dp[n][i]!=INF) { printf("%d\n", i); break; } } return 0;}