HDU5543Pick The Sticks(01背包)

/*【题意】
给你一个长度为m（[1,2000]）的长条状容器。
然后我们有n（[1,1000]）段木棒。
第i段木棒有一个长度a[i].l和价值a[i].v。
我们希望把尽可能大价值的木棒放到容器中，使得所有木棒的重心都在容器内
要求木棒不能重叠。【分析】
用f[i][j][u]表示现在处理到前i根木棍，它们在容器内占据的长度为j，且有u条木棍悬挂在外的最大价值。
这个DP多加了一个维度u，显然u的取值范围是[0,2]
同样采取使得half=原长len，使得len=原长len的2倍的避免小数的策略。
那么我们有状态转移方程
gmax(f[i][j][u],f[i-1][j-a[i].len][u]+a[i].val);
gmax(f[i][j][u],f[i-1][j-a[i].half][u-1]+a[i].val);
这样从所有的子状态中更新答案。注意，我们可以使用三维数组表示空间，这里也可以下降为只有[j][u]，第一维度的i可以省略。
这样压缩空间的做法需要注意保证拓扑序。要无环，要避免同一个木棍多次更新状态。
我们只要改变枚举顺序，使得j降序。
因为每个物品的空间都至少为1，所以不论u的顺序，这里就可以保证，一定不会重复更新。【时间复杂度&&优化】
O(n^2)
*/#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1005, M = 4005;
struct Node
{int h, l, v;bool operator < (const Node &other) const{return h < other.h;}
}a[N];
LL dp[M][3];
LL solve()
{int n, m;scanf("%d%d", &n, &m);m<<=1;LL ans = 0;memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; i++){scanf("%d%d", &a[i].h, &a[i].v);a[i].l = (a[i].h<<1);if(a[i].v > ans) ans = a[i].v;}sort(a+1, a+n+1);while(n>=1&&a[n].h>=m) n--;for(int i = 1; i <= n; i++)for(int j = m; j >= a[i].h; j--)for(int u = 0; u <= 2; u++){if(j>=a[i].l) dp[j][u] = max(dp[j][u], dp[j-a[i].l][u] + a[i].v);if(u) dp[j][u] = max(dp[j][u], dp[j-a[i].h][u-1]+a[i].v);}ans = max(ans, dp[m][2]);return ans;
}
int main()
{int t, kase = 1;scanf("%d", &t);while(t--){printf("Case #%d: %I64d\n", kase++, solve());}return 0;
}