HNU 12309 Flooring

HNU_12309

    除去长度为L的木板，这个题目就可以看成4种物品装入背包，问最少几个背包能够装下。

    在划分阶段的时候如果按一个背包一个背包装的话，这样决策的选择就会变得很多，而如果按一个物品一个物品去装的话，那么决策就很少了。

    在记录状态的时候必然要纪律剩余物品的情况，于是不妨开一个四维数组f[i][j][k][l]，表示剩余的物品数分别为i、j、k、l时最少需要的背包数，但只记录这些信息还是不够的，我们还需要当前在装的这个背包还剩余多少容量，于是可以再开一个四维数组g[i][j][k][l]，表示在背包数量最少的前提下，当前背包剩余的最大容量是多少。

    在决策的时候，只要分别对4种物品进行尝试即可，如果当前这个物品不能放到当前这个背包中，那么就尝试新开一个背包。

    最后再加上中间所有长为L的木板数即可。

#include<stdio.h>
#include<string.h>
#define MAXD 35
#define INF 0x3f3f3f3f
int N, M, A, B, L, a[4], b[2], num[4], f[MAXD][MAXD][MAXD][MAXD], g[MAXD][MAXD][MAXD][MAXD];
void update(int i, int j, int k, int l, int pi, int pj, int pk, int pl, int x)
{
    if(g[pi][pj][pk][pl] >= a[x])
    {
        if(f[pi][pj][pk][pl] < f[i][j][k][l] || (f[pi][pj][pk][pl] == f[i][j][k][l] && g[pi][pj][pk][pl] - a[x] > g[i][j][k][l]))
            f[i][j][k][l] = f[pi][pj][pk][pl], g[i][j][k][l] = g[pi][pj][pk][pl] - a[x];
    }
    else
    {
        if(f[pi][pj][pk][pl] + 1 < f[i][j][k][l] || (f[pi][pj][pk][pl] + 1 == f[i][j][k][l] && L - a[x] > g[i][j][k][l]))
            f[i][j][k][l] = f[pi][pj][pk][pl] + 1, g[i][j][k][l] = L - a[x];
    }
}
void solve()
{
    int i, j, k, l;
    a[0] = A <= N ? A : 0, a[1] = A <= N ? (N - A) % L : N % L, a[2] = B <= N ? B : 0, a[3] = B <= N ? (N - B) % L : N % L;
    num[0] = (M + 1) / 2, num[1] = (M + 1) / 2, num[2] = M / 2, num[3] = M / 2;
    b[0] = A <= N ? (N - A) / L : N / L, b[1] = B <= N ? (N - B) / L : N / L;
    b[0] *= (M + 1) / 2, b[1] *= M / 2;
    for(i = 0; i <= num[0]; i ++)
        for(j = 0; j <= num[1]; j ++)
            for(k = 0; k <= num[2]; k ++)
                for(l = 0; l <= num[3]; l ++)
                {
                    if(!i && !j && !k && !l)
                    {
                        f[0][0][0][0] = 0, g[0][0][0][0] = 0;
                        continue;
                    }
                    f[i][j][k][l] = INF, g[i][j][k][l] = -1;
                    if(i)
                        update(i, j, k, l, i - 1, j, k, l, 0);
                    if(j)
                        update(i, j, k, l, i, j - 1, k, l, 1);
                    if(k)
                        update(i, j, k, l, i, j, k - 1, l, 2);
                    if(l)
                        update(i, j, k, l, i, j, k, l - 1, 3);
                }
    printf("%d\n", f[num[0]][num[1]][num[2]][num[3]] + b[0] + b[1]);
}
int main()
{
    while(scanf("%d%d", &M, &N) == 2)
    {
        scanf("%d%d%d", &A, &B, &L);
        solve();
    }
    return 0;
}