Poj 1170 Shopping Offers (DP_狀态壓縮DP)

題目連結：http://poj.org/problem?id=1170

題目大意：給定一個訂單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

代碼：

#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原創，但可以轉載，因為我們是兄弟。