学步园

POJ 1170
IOI95的题目了，比较简单。题目大意是说要买一些商品，而商店提供了一些组合购买的打折方案，你不能多买东西，问怎样购买最省。怎样表示状态呢？其实很自然想到把当前你要买哪些东西，并且它们分别要买多少作为状态，那么方程就写成：

现在的问题就成了如何在实现的时候来表示S。由于只买5种不同商品，每种的数量最多为5件，于是考虑用6进制表示状态，其中权位及表示商品种类，系数就是商品数量，然后再把这个数压缩成一个10进制数，于是在程序中就好处理了。
这样每次转移时先把该状态还原成六进制，然后转移后再压缩即可。时间为O(m*k*6^n)，空间O(6^n)。

没用到状态压缩，题目就是用node表示一种方案，把所有方案都存起来，再对方案进行0-1背包式的放入，选择最优解！事实上那个5维数组可以用状态来表示

#include <iostream><br /> using namespace std;</p> <p>int b,s;<br /> int dp[6][6][6][6][6];</p> <p>struct node<br /> {//一种销售方案<br /> int n[6]; //各个物品卖多少个<br /> int sum; //该方案的价值<br /> };<br /> node ideal[200];<br /> int code[1000];<br /> int num[10];</p> <p>void Init()<br /> {<br /> int c,k,p,n;<br /> int i,j;<br /> memset(ideal,0,sizeof(ideal));<br /> // scanf("%d",&b);<br /> for(i=1;i<=b;i++)<br /> {<br /> scanf("%d%d%d",&c,&num[i],&p);<br /> code[c] = i;<br /> ideal[i].n[i] = 1;<br /> ideal[i].sum = p;<br /> }<br /> scanf("%d",&s);<br /> for(i=1;i<=s;i++)<br /> {<br /> scanf("%d",&n);<br /> for(j=1;j<=n;j++)<br /> {<br /> scanf("%d%d",&c,&k);<br /> ideal[b+i].n[code[c]] = k;<br /> }<br /> scanf("%d",&p);<br /> ideal[b+i].sum = p;<br /> }</p> <p>}</p> <p>int getnum(int x1,int x2,int x3,int x4,int x5)<br /> {<br /> int i;<br /> if(dp[x1][x2][x3][x4][x5] > -1)<br /> {<br /> return dp[x1][x2][x3][x4][x5];<br /> }<br /> int min = 0x7fffffff;<br /> for(i=1;i<=s+b;i++)<br /> {<br /> if(x1>=ideal[i].n[1] && x2>=ideal[i].n[2] && x3>=ideal[i].n[3] && x4>=ideal[i].n[4] && x5>=ideal[i].n[5])<br /> {<br /> int temp = ideal[i].sum + getnum(x1-ideal[i].n[1],x2-ideal[i].n[2],x3-ideal[i].n[3],x4-ideal[i].n[4],x5-ideal[i].n[5]);<br /> if(temp < min)<br /> min = temp;<br /> }<br /> }<br /> dp[x1][x2][x3][x4][x5] = min;<br /> return min;<br /> }</p> <p>int main()<br /> {<br /> while(scanf("%d",&b)!=EOF)<br /> {<br /> Init();<br /> memset(dp,-1,sizeof(dp));<br /> dp[0][0][0][0][0] = 0;<br /> int numm = getnum(num[1],num[2],num[3],num[4],num[5]);<br /> printf("%d/n",numm);<br /> }<br /> return 0;<br /> }<br />

POJ 1691
这题看起来复杂，其实就是要你找到一种表示当前棋盘状态的方法。由于只有15个方块，很自然又想到了二进制表示，第k位为0表示第k块矩形已经作色，为1就还没有。还有先预处理一个有向图，s->t表示t在s的上方，于是每次转移的时候枚举颜色，然后看一次最多能涂多少（可以证明每次都贪心尽量涂是最好的策略），递归处理就好了。

POJ 1185
NOI01的题目，相当经典的问题。这题其实和CEOI的bugs integreted inc是一样的，同时和上面第一题的方法也一样，就是用三进制来表示当前位置的状态，0表示这格安放炮兵，1表示上面一格有，2表示上面两格有，这样上下的情况就解决了，转移时再枚举一下邻里的情况就可以。还要注意使用滚动数组优化空间，时间O(n*2^m*3^m)，空间O(3^m)。

最后再来说下关于实现的问题。
最常用和直接的方法就是记忆化搜索，非常容易实现，传递压缩后的状态即可。当状态规模小，而转移又比较多并且是二进制压缩时时，还可以使用迭代状态空间的办法（iterative through the state space），就是枚举每种组合，然后转移。