poj 1170Shopping Offers解题报告

很经典的状态dp，这道题基本上体现了状态dp的全部处理过程，状态进制的确定过程，主要是根据题中的数据范围，状态产生要根据输入的状态产生，中间状态合法性判断，对状态的计算处理，然后才是dp里的最优子结构选择问题，当然了要保证一个选择只有一种状态，这是肯定的。最后就是结果的处理过程。

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define inf 0x7fffffff
 5 #define min(x,y) x<y?x:y
 6 using namespace std;
 7 int b[7]={1,6,36,216,1296,7776,46656};
 8 struct good
 9 {
10     int code,num,price;
11 }basket[5];
12 struct sta
13 {
14     int state;
15     int price;
16 }offer[100];
17 int n,num,state;
18 int flag[1000];
19 int dp[46656];
20 bool cheack(int p1,int p2)//两个状态能否相加的合法性判断
21 {
22     int i;
23     for(i=0;i<n;i++)
24     {
25         if((p1%6+p2%6)>basket[i].num)
26         return false;
27         p1/=6;
28         p2/=6;
29     }
30     return true;
31 }
32 int cal(int p)//状态产生价值计算
33 {
34     int i;
35     int sum=0;
36     for(i=0;i<n;i++)
37     {
38         sum+=(p%6)*basket[i].price;
39         p/=6;
40     }
41     return sum;
42 }
43 int main()
44 {
45     int i,j,k,ans,num;
46     while(scanf("%d",&n)!=EOF)
47     {
48         state=0;
49         for(i=0;i<1000;i++)
50         flag[i]=6;
51         memset(basket,0,sizeof(basket));
52         for(i=0;i<n;i++)
53         {
54             scanf("%d%d%d",&basket[i].code,&basket[i].num,&basket[i].price);
55             flag[basket[i].code]=i;
56             state+=basket[i].num*b[i];//状态的产生
57         }
58         scanf("%d",&num);
59         int goodnum,temp,tempco;
60         memset(offer,0,sizeof(offer));
61         for(i=0;i<num;i++)
62         {
63             scanf("%d",&goodnum);
64             for(j=0;j<goodnum;j++)
65             {
66                 scanf("%d%d",&tempco,&temp);
67                 offer[i].state+=b[flag[tempco]]*temp;//单个状态的产生
68             }
69             scanf("%d",&offer[i].price);
70         }
71         for(i=0;i<=state;i++)
72         dp[i]=inf;
73         dp[0]=0;
74         for(i=0;i<num;i++)
75         for(j=0;j<=state;j++)
76         {
77             if(dp[j]==inf)
78             continue;
79             if(j+offer[i].state<=state&&cheack(j,offer[i].state))//最优值选择
80             dp[j+offer[i].state]=min(dp[j]+offer[i].price,dp[j+offer[i].state]);
81         }
82         ans=inf;
83         for(i=0;i<=state;i++)//最后产生结果的处理
84         {
85             if(dp[i]==inf)
86             continue;
87             ans=min(dp[i]+cal(state-i),ans);
88         }
89         printf("%d\n",ans);
90     }
91     return 0;
92 }