【题目概述】罗骰子游戏，N（1<=N<=10）个骰子，每个骰子有六个编号为0~5的面，现在要求把骰子罗成一摞，且要求两个骰子重叠的面的编号相等，求罗成的长方体四个侧面中最大面积的侧面的面子。

【题目分析】将骰子罗列，求最大的侧面，还要求相邻两个骰子接触面编号相等？！该如何解决呢？看图，先来解决相邻的两个面编号相等的问题！有图得到  因此，可以很容易的判断一个面的对立面！第一个问题解决。

题目中给出了这个条件是狠重要就是，就是一个骰子可以左右转动，这提示我们水平的四个面中编号最大的面总是可以转到一个面上的。由此，我们可以确定那个面和其余骰子接触的时候，确定这个骰子提供的最大的面积。

确定这两个起初看是不确定的问题，下面的算法就是比较通俗的了。

设  表示最大值，其中，i为已放入的骰子，第j个骰子的第k个面朝上。则

若只放一个筛子， , 其中b[i][j]表示第i个骰子的第j个面向上放置贡献的最大值，可以预处理的时候求出。

对于已放置的骰子，可以转移到为放置的上面，所以，枚举合法的状态，然后添加骰子，同时更新状态值。

【详细代码】下面是AC的代码。

//Name: pku_2596_Dice Stacking

#include <iostream>

using namespace std;

#define max(a, b)((a)=((a)>(b)?(a):(b)))

const int f[6]={5,4,3,2,1,0};

int a[10][10], b[10][10];

int dp[1<<10][10][6], n, ans;

int main() {

    //freopen("in.in", "r", stdin);

    int ca, i, j, k, p, q, t, kn;

    scanf("%d", &ca);

    while(ca-- && scanf("%d", &n)) {

        kn = 1<<n;

        memset(b, 0, sizeof(b));

        for(i = 0; i < n; i++) {

            for(j = 0; j < 6; j++) scanf("%d",a[i]+j);

            for(j = 0; j < 6; j++)

                for(k = 0; k < 6; k++) if(k!=j && k != f[j])

                    max(b[i][j], a[i][k]);

        }

        memset(dp, -1, sizeof(dp));

        for(i = 0; i < n; i++)

            for(j = 0; j < 6; j++) dp[1<<i][i][j] = b[i][j];

        for (i = 0; i < kn; i++) {

            for (j = 0; j < n; j++) {

                for (k = 0; k < 6; k++) if(dp[i][j][k] != -1) {

                    for(p = 0; p < n; p++) if(!(i & (1<<p))) {

                        for (q = 0; q < 6; q++) if(a[j][k] == a[p][f[q]]) {

                            t = i|(1<<p);

                            max(dp[t][p][q], dp[i][j][k] + b[p][q]);

                        }//ifq

                    }//ifp

                }//ifk

             }//fj

         }//fi

         ans = 0;

         for (i = 0; i < n; i++)

            for (j = 0; j < 6; j++) max(ans, dp[kn-1][i][j]);

         printf("%d\n", ans);

    }

    return 0;

}

【题目概述】告诉平面上一些点，从中选择部分点出来，要求不能选择相邻的点，求所有的方案数。

【题目分析】学过gohst—wei的代码风格之后，第一道小练兵。花的时间虽然长了点，但是，感觉还不错。

1.         首先还是分析采取由上而下，逐行分析的策略。

2.         我们发现，影响当前行的状态的只有上一行，即上一行和下一行的要满足相邻不相等原则。

3.         设 表示前i行的方案数，且第i行的状态为s.

转移方程：

（其中，t为上一行的某个与当前行不相冲突的状态）

4.         时间复杂度为 显然这样的复杂度为不满足条件的。因此需要优化

5.         我们发现，题目中有一个限制的条件是没用到的。就是同一行也不满足相邻不可取的。由此，我们可以实现预处理，剔除掉多余的状态，这样，最后的每行合法的状态，最多只有367个。

【题目代码】下面是AC的代码。

//Name: pku_3254_Corn Fields

#include <iostream>

using namespace std;

const int maxs = 1<<12;

const int mod = 100000000;

int map[13][13], n, m;

int stk[maxs], sn;

int dp[2][maxs];

inline bool one(int i, int j) { return (i&(~(1<<j))) != i;}

bool check(int i, int j) {

    if (j > 0 && one(i, j-1)) return 0;

    if (j < m-1 && one(i, j+1)) return 0;

    return 1;

}

void Proced(int km, int m) {

    sn = 0; int i, j;

    for (i = 0,j; i < km; i++) {

        for (j = 0; j < m; j++)

            if(one(i, j) && !check(i,j)) break;

        if (j == m) stk[sn++] = i;

    }

   // for (i = 0; i < sn; i++) printf("stk[%d] = %d\n", i, stk[i]);

}

void SCDP() {

    int i, j, s1, s2, k1, k2, e1 = 0, e2 = 1;

    for (j = 0; j < sn; j++) dp[0][stk[j]] = 0;

    dp[0][0] = 1;

    for (i = 1; i <= n; i++) {

        for (j = 0; j < sn; j++) dp[e2][stk[j]] = 0;

        for (k1 = 0; k1 < sn; k1++) {

            for (k2 = 0; k2 < sn; k2++) {

                 s1 = stk[k1]; s2 = stk[k2];

                 if(s1 & s2)continue;

                 for(j = 0; j < m; j++)

                    if (!map[i][j] && one(s2, j)) break;

                 if (j == m) {

                    dp[e2][s2] = (dp[e2][s2]+dp[e1][s1])%mod;

                }

            }

        }

        e1 ^= 1; e2 ^= 1;

    }

    int ans = 0;

    for (k1 = 0; k1 < sn; k1++)

        ans = (ans + dp[e1][stk[k1]])%mod;

    printf("%d\n", ans);

}

int main() {

    freopen("in.in", "r", stdin);

    scanf("%d %d", &n, &m);

    Proced(1<<m, m);

    for(int i = 1; i <= n; i++)

        for (int j = 0; j < m; j++)

             scanf("%d", map[i]+j);

    SCDP();

    return 0;

}

【题目概述】求N（N<=10）个子串的最短和串，且不会发生一个完全包涵另外一个的现象。

【题目分析】简单的状态DP问题，一开始想用字符串的思想解决，发现状态之间，不好变换。正好自己做压缩DP的专题，还是，用这个方法吧！

1.         对于每个字符串的放置，和她有直接影响的是上一个字符的放置情况。由此，我们可以建立一个状态转移方程

设  表示当前状态s以第i个字符串结尾产生的最小和串的长度。则

2.         若s只包含一个串的时候， 其中len[i]表示第i个子串的长度。

3.         否则，如果当前的状态合法，且s状态集中，不包含有j串，那么,， 记

a)        如果 其中，com[I, j] 表示第i个串之后是第j个串的公共子串的长度。

b)        否则，不处理。

4.         最后的结果就是，    i是所有的子串。

【题目代码】：

//Name: pku_1699_Best Sequence

#include <iostream>

#include <cstring>

using namespace std;

const int inf = 1<<20;

const int maxn = 1<<10;

char str[10][20];

int len[10], com[20][20], n, m;

int dp[maxn][10], ans;

void Link(int x, int y) {

    int i, j, k, mlen = min(len[x], len[y]);

    for (k = mlen; k >= 0; k--) {

        for (i = len[x]-k, j = 0; i < len[x]; i++, j++)

            if (str[x][i] != str[y][j]) break;

        if (i == len[x]) {

            com[x][y] = k; break;

        }

    }

    for (k = mlen; k >= 0; k--) {

        for (i = len[y]-k, j = 0; i < len[y]; i++, j++)

            if (str[y][i] != str[x][j]) break;

        if (i == len[y]) {

            com[y][x] = k; break;

        }

    }

}        

int main() {

   // freopen("in.in", "r", stdin);

    int t, i, j, s, r; scanf("%d", &t);

    while(t-- && scanf("%d", &n)) {

        memset(com, 0, sizeof(com));

        for(i = 0; i < n; i++) {

             scanf("%s", str+i);

             len[i] = strlen(str[i]);

             for (j = 0; j < i; j++) Link(i, j);

        }

       // for(i = 1; i < n; i++) printf("%d\n", com[i-1][i]);

        for(i = 1; i < 1<<n; i++)

            for (j = 0; j < n; j++) dp[i][j] = inf;

        for(i = 0; i < n; i++) dp[1<<i][i] = len[i];

        for(s = 1; s < 1<<n; s++) {

            for (i = 0; i < n; i++) if(s&(1<<i)) {

                for(j = 0; j < n; j++) if(i!=j && !(s&(1<<j))) {

                    r = s|(1<<j);

                    dp[r][j] = min(dp[r][j], dp[s][i] - com[i][j] + len[j]);

                  // printf("dp[%d][%d] = %d\n", r, j, dp[r][j]);

                 }

             }

        }

     // for(i = 0; i < n; i++) printf("%d\n", dp[s-1][i]);

        ans = inf;

        for(i = 0; i < n; i++)

            if (dp[s-1][i] < ans) ans = dp[s-1][i];

        printf("%d\n", ans);

   }

   return 0;

}

【题目概述】告诉一张地图，地图上有N(2<=2<= 30)个城市，由一个城市到另外一个城市的唯一交通工具是马车，不同型号的马车花费的时间（这里的时间计算用两地的距离除以该马车骂的数量，马越多越快）不一样。现在给你N(1<=N<=8)两马晨，每辆马车告诉马的数量，求有一个城市到另外一个城市的最短时间。

【题目分析】参考了hobby的代码，和froeverLin提示，在这里予以说明。

l 像是一个最短路问题，但是增加了限制条件，解法DP毋庸置疑，给定马车的数量<= 8， 状态压缩DP.

l 要求的仅仅是最短的时间，没有求分配方案，这无疑使问题简单话了。

l 影响节点（城市）之间的花费的唯一变化因素是马的数量（距离是固定的）。

l  设 表示当前状态为s，走到城市j的最小时间。

状态转移方程，为 对于任何一个与j相连的节点k。

其中， r为和k相连的城市， r为不在s中的某个马车的加入后的状态， t[w]为该马车的马匹数。

l 初始化问题。

n 由于求的是最小值，我们初始化dp为某个最大值。

for(p = 1; p < (1<<n); p++)

            for(i = 0; i < m; i++) dp[p][i] = inf;

n 由于每次都是从a开始的，所以初始化的时候要初始化和a与关系的边的转移。

        for (i = 0; i < m; i++) if(map[a][i] != -1)

            for(k = 0; k < n; k++) dp[1<<k][i] = map[a][i]/t[k];

【题目代码】

//Name: pku_2686_Traveling by Stagecoach

// dp[i][j]表示当前使用的票的状态为i到达了j城市的最少用时

// 若第k个城市与j相连通，且，枚举枚举票数最少的

#include <iostream>

using namespace std;

#define inf 1<<30

int map[30][30];

int n, m, p, a, b, d, r, q;

double dp[1<<8][30], t[30], tmp, ans;

int main() {

   // freopen("in.in", "r", stdin);

    int i, j, k, x, y;

    while(scanf("%d%d%d%d%d",&n,&m,&p,&a,&b) != EOF) {

        if (!(n||m||p||a||b)) break;

        a--; b--;

        for(i = 0; i < n; i++) scanf("%lf", t+i);

        memset(map, -1,sizeof(map));

        for (i = 1; i <= p; i++) {

            scanf("%d %d %d", &x, &y, &d); x--;y--;

            map[x][y] = map[y][x] = d;

        }

        for(p = 1; p < (1<<n); p++)

            for(i = 0; i < m; i++) dp[p][i] = inf;

        for (i = 0; i < m; i++) if(map[a][i] != -1)

            for(k = 0; k < n; k++)

                 dp[1<<k][i] = map[a][i]/t[k];

        for (p = 1; p < (1<<n); p++) {

            for (j = 0; j < m; j++) if(dp[p][j] != inf) {

                for (k = 0; k < m; k++) if(k!=j && map[j][k]!=-1) {

                    for (r = 0; r < n; r++) if(!(p&(1<<r))) {

                        q = p + (1<<r);

                        tmp = dp[p][j] + map[j][k] /t[r];

                        if (dp[q][k] > tmp) dp[q][k] = tmp;

                    }

                }

            }

       }

       ans = inf;

       for (p = 1; p < (1<<n); p++)

            if(dp[p][b] < ans) ans = dp[p][b];

       if(ans == inf) printf("Impossible\n");

       else printf("%lf\n", ans);

   }

}