ZOJ2575 Full of Painting 动态规划

题意：给定N个限定了边长范围的正方形，现在要把它们全部铺到长度固定，高度不限的墙上，一共有N种颜色一一对应使用，告诉每种颜色的单位面积价格。问铺满墙的最少开销是多少？只要长度为L的墙被覆盖了所有长度即可。

解法：该题有个良好的性质为不论给定的正方形的顺序如何，都不影响最后的结果。设状态f[i][j][k]表示放置到第i个覆盖长度为j，且颜色选择为k时的最少开销。其中k是状态压缩的选择方案。那么有动态规划方程f[i][j][k] = min(f[i][j][k], f[i-1][j-p][k']) 其中p为第i个正方形合法的取值边长，k'为选择了i-1种颜色的方案，也是是k‘中有i-1个位置为1。最后输出f[i][L][final]其中final为全部颜色均选取。

代码如下：

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

int N, K;
int bit[50], L[10], H[10];
double f[205][50];
double pri[10];

int get(int x) {
    int cnt = 0;
    for (int i = 0; i < 5; ++i) {
        if (x & (1 << i)) ++cnt;
    }
    return cnt;
}

void pre() {
    for (int i = 0; i <= 40; ++i) {
        bit[i] = get(i);    
    }
}

void solve() {
    for (int i = 0; i <= K; ++i) {
        for (int j = 0; j <= 31; ++j) {
            f[i][j] = 1e30;
        }
    }
    f[0][0] = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = K; j >= L[i]; --j) {
            for (int p = L[i]; p <= j && p <= H[i]; ++p) {
                for (int k = 0; k <= 31; ++k) {
                    if (bit[k] != i-1 || f[j-p][k] == 1e30) continue;
                    for (int h = 0; h < N; ++h) {
                        if (!(k & (1 << h))) {
                            f[j][k|(1<<h)] = min(f[j][k|(1<<h)], f[j-p][k] + p*p*pri[h+1]);
                        }
                    }
                }
            }
        }
    }
    if (f[K][(1<<N)-1] == 1e30) {
        puts("Impossible");
    } else {
        printf("%.3f\n", f[K][(1<<N)-1]);    
    }
}

int main() {
    pre();
    while (scanf("%d %d", &N, &K) != EOF) {
        for (int i = 1; i <= N; ++i) {
            scanf("%lf", &pri[i]);
        }
        for (int i = 1; i <= N; ++i) {
            scanf("%d %d", &L[i], &H[i]);
        }
        solve();
    }
    return 0;
}