2015 CCPC D 문제【0-1 가방 변형】

제목
제목: n(<=1000)개의 금괴가 있는데, 금괴마다 상응하는 길이와 가치가 있습니다. 지금 L(<=2000)의 접시에 금괴를 접어 놓을 수 없도록 하세요. 그리고 중심은 접시(단점 포함)에 있어야 합니다. 얻을 수 있는 최대 가치를 구하세요.
사고방식: 우리는 임의로 k(k<=2)개의 금괴를 선택하여 절반의 길이(절반을 잘라서 놓는)로 그들의 가치를 얻을 수 있다.
이렇게 dp[i][j][k]로 i번 금괴 가방의 남은 용량이 j인 경우 k번 금괴를 반으로 잘라 놓으면 가장 큰 가치를 얻을 수 있음을 나타낸다.
상태 이동 방정식
dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][j-len[i]][k]+val[i], dp[i-1][j-len[i]/2][k-1]+val[i]).
아래는 그냥 0-1 가방이면 돼요.
주의:len[i]/2는 부동점수가 나타날 수 있습니다. 모든 필요는len[]*=2 & L *=2입니다.
AC 코드:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#define lson o<<1|1, l, mid
#define rson o<<1, mid+1, r
#define ll o<<1
#define rr o<<1|1
#define INF 0x3f3f3f3f
#define eps 1e-8
#define debug printf("1
")
#define MAXN 1010
#define MAXM 100000
#define LL long long
#define CLE(a, b) memset(a, (b), sizeof(a))
#define W(a) while(a--)
#define Ri(a) scanf("%d", &a)
#define Pi(a) printf("%d
", (a))
#define Rl(a) scanf("%lld", &a)
#define Pl(a) printf("%lld
", (a))
#define Rs(a) scanf("%s", a)
#define Ps(a) printf("%s
", (a))
using namespace std;
LL dp[5000][3];
LL len[MAXN], val[MAXN];
int main()
{
    int t, kcase = 1;
    Ri(t);
    W(t)
    {
        int N, L;
        Ri(N); Ri(L);
        for(int i = 0; i < N; i++)
            Rl(len[i]), Rl(val[i]);
        if(N == 1)
        {
            printf("Case #%d: %lld
", kcase++, val[0]);
            continue;
        }
        L *= 2;
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < N; i++)
        {
            len[i] *= 2;
            for(int j = L; j >= len[i]/2; j--)
            {
                for(int k = 0; k <= 2; k++)
                {
                    if(k >= 1)
                        dp[j][k] = max(dp[j][k], dp[j-len[i]/2][k-1]+val[i]);
                    if(j >= len[i])
                        dp[j][k] = max(dp[j][k], dp[j-len[i]][k]+val[i]);
                }
            }
        }
        LL ans = 0;
        for(int i = 0; i <= 2; i++)
            ans = max(ans, dp[L][i]);
        printf("Case #%d: %lld
", kcase++, ans);
    }
    return 0;
}