http://acm.uestc.edu.cn/#/problem/show/1218
既然二维dp表示不了,就加一维表示是否在边界放置,放置一个,两个。有一个trick就是如果只放一根,那么多长都可以。
wa了好多次(囧)
开始因为l[i]/2会出现小数,没注意,把所有的长度都x2就可以解决。
又wa了n次因为没注意j-l[i]时没加判断,为什么不是RE呢!不开心。。。
/*********************************************
Memory: 1140 KBTime: 3976 MS
Language: C++Result: Accepted
*********************************************/
#include <iostream>
#include <cstring>using namespace std;typedef long long ll;int l[1005];
int v[1005];
ll dp[4005][5];int main()
{
int t;
cin >> t;
int cas = 0;
while (t--)
{
cas++;
int n, L;
cin >> n >> L;
L *= 2;
ll ans = 0;
for (int i = 0; i < n; ++i)
{
cin >> l[i] >> v[i];
l[i] *= 2;
ans = max(ans, (ll)v[i]);
}
memset(dp, 0, sizeof dp);
for (int i = 0; i < n; ++i)
{
for (int j = L; j >= l[i] / 2; --j)
{
dp[j][2] = max(dp[j][2], dp[j - l[i] / 2][1] + v[i]);
if (j >= l[i]) dp[j][2] = max(dp[j][2], dp[j - l[i]][2] + v[i]);
dp[j][1] = max(dp[j][1], dp[j - l[i] / 2][0] + v[i]);
if (j >= l[i]) dp[j][1] = max(dp[j][1], dp[j - l[i]][1] + v[i]);
if (j >= l[i]) dp[j][0] = max(dp[j][0], dp[j - l[i]][0] + v[i]);
}
}
ans = max(ans, dp[L][2]);
cout << "Case #" << cas << ": " << ans << endl;
}
return 0;
}/**
Input:
50
2 3
1 2
2 33 7
4 1
2 1
8 13 7
4 2
2 1
8 43 5
4 1
2 2
8 91 1
10 3Output:
5
2
6
11
3*/