Poj 1170 Shopping Offers (DP_状态压缩DP)

题目大意：给定一个订单n种商品，每种商品有个初始价格pri，初始数量numi，再给定m种组合，这些组合会得到便宜的价格。最后问怎么搭配使得总价格最少。

解题思路：搜状态压缩的题目时搜到关于这题的解题报告，名曰《经典状态压缩DPxxx》，然后我很认真地做了这题，还想好好吸收下，没想到是水题，囧。
    先将每种物品用一个六进制数表示，第1个物品表示为st1 = 1，第2个物品表示为st2 = 6....，这样订单上的物品总状态为nn = num1 * 1 + num2 * 6 ..
    这题其实是背包，n+m种物品，前n种物品体积为sti，价值为pri，后m种物品体积为组合内物品压缩成的一个状态stmi，价值为更便宜的那个价格。
    最后用完全背包来写就好。

测试数据：
Input:
2
7 3 2
8 2 5
2
1 7 3 5
2 7 1 8 2 10
OutPut
14

代码：
[cpp]
#include <stdio.h> 
#include <string.h> 
#define MAX 110000 
#define INF (1<<29) 
#define min(a,b) ((a)<(b)?(a):(b)) 
 
 
struct product { 
     
    int code,st,num,price; 
}arr[MAX],special[MAX]; 
int dp[MAX],hash[1000],n,m,nn,ans; 
int ST[10] = {1,6,36,216,1296,7776,46656,279936}; 
 
 
void Initial() { 
 
    ans = nn = 0; 
    memset(hash,-1,sizeof(hash)); 
    for (int i = 0; i < ST[6]; ++i) 
        dp[i] = INF; 
} 
void Solve_DP() { 
 
    int i,j,k; 
    dp[0] = 0; 
    for (i = 0; i <= nn; ++i) 
        for (j = 0; j < n + m; ++j) 
            dp[i+arr[j].st] = min(dp[i+arr[j].st],dp[i]+arr[j].price); 
    ans = min(ans,dp[nn]); 
} 
 
 
int main() 
{ 
    int i,j,k,tp,num,code; 
 
 
    while (scanf("%d",&n) != EOF) { 
 
        Initial(); 
        for (i = 0; i < n; ++i) { 
 
            scanf("%d%d%d",&arr[i].code,&arr[i].num,&arr[i].price); 
            arr[i].st = ST[i]; 
            hash[arr[i].code] = i; 
            nn += arr[i].num * arr[i].st; 
            ans += arr[i].num * arr[i].price; 
        } 
        scanf("%d",&m); 
        for (i = 0; i < m; ++i) { 
 
            scanf("%d",&k); 
            arr[i+n].st = 0; 
            for (j = 0; j < k; ++j) { 
 
                scanf("%d%d",&code,&num); 
                if (hash[code] == -1) continue; 
                arr[i+n].st += arr[hash[code]].st * num; 
            } 
            scanf("%d",&arr[i+n].price); 
        } 
 
 
        Solve_DP(); 
        printf("%d/n",ans); 
    } 
} 

本文ZeroClock原创，但可以转载，因为我们是兄弟。