题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5543
题意：给你一根长为m的长木板和一些小木棒，每一根小木棒有它的长度和价值，这些小木棒要放在长木板上并且每一根小木棒的重心要在长木板上（即可以露出一半的长），问最大价值是多少。
dp[i][j][k] 表示前i个小棒放到长度为j的木板上，其中有k个小棒放在边沿部分, 边沿部分的小棒需要尽量放在木板外面（贪心思维），所以放在边沿的木棒落在木板上的长度为l/2。然后就是简单的01背包问题了。
tip：放一个小棒的情况需要预处理，因为不管木板长度为多少，一个小棒总是能平衡的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 1010
#define maxl 4010
using namespace std; typedef long long LL; LL dp[maxl][];
int len[maxn], cost[maxn]; int main(void)
{
int ncase, n, l, ca = ;
scanf("%d", &ncase);
while (ncase--)
{
memset( dp, , sizeof( dp));
LL ans = ;
scanf("%d %d", &n, &l);
l *= ;
for (int i = ; i < n; ++i)
{
scanf("%d %d", len + i, cost + i);
len[i] *= ;
ans = max( ans, (LL)cost[i]);
} for (int i = ; i < n; ++i)
{
for (int j = l; j >= len[i]/; --j)
{
for (int k = ; k < ; ++k)
{
if (j >= len[i])
dp[j][k] = max( dp[j][k], dp[j-len[i]][k] + cost[i]);
if (k > )
dp[j][k] = max( dp[j][k], dp[j-len[i]/][k-] + cost[i]);
ans = max( ans, dp[j][k]);
}
}
}
printf("Case #%d: %lld\n", ca++, ans);
}
return ;
}