SSL 2695_购买_dp

lzusa 发布于 2017-08-15 890 次阅读

题目描述

BPM想要购买m种物品，每种物品只用购买一件。现在一共有n家商店，但走到第i家商店的路费为d[i]，而在第i家商店购买第j种物品的花费为c[i,j]。问你最少需要花费多少钱。

 

思路

转移显然的状压dp

就是从上一家点向下转移，枚举商品和状态即可

#include 
#include 
#include 
using namespace std;
#define fill(x, y) memset(x, y, sizeof(x))
#define min(x, y) (x) < (y) ? (x) : (y)
int f[101][1 << 16], a[101][17];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
            scanf("%d", &a[i][j]);
    }
    fill(f, 31);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= (1 << m) - 1; j++)
            f[i][j] = f[i - 1][j] + a[i][0];
        for (int j = 1; j <= m; j++)
            for (int k = 0; k <= (1 << m) - 1; k++)
                if (~k&(1 << j - 1))
                    f[i][k | (1 << j - 1)] = min(f[i][k | (1 << j - 1)], f[i][k] + a[i][j]);
        for (int j = 0; j <= (1 << m) - 1; j++)
            f[i][j] = min(f[i][j], f[i - 1][j]);
    }
    printf("%d\n", f[n][(1 << m) - 1]);
}

 

 

]]>