UVa 10604 Chemical Reaction（hash记忆化搜索）

题意：

每组数据开始有一个整数n，表示有n种试剂（最多6种）。接下来的n*n行列出来了每种试剂混合产生的化合物以及放出的热量。
然后一个整数m，代表有m个试管(最多10个)。
接下来一行有m个数，表示m个试管里分别装了哪几种试剂。

问怎么组合能产生最少的热量。测试样例之间用/分开，结果用.表示

思路：

http://www.cnblogs.com/staginner/archive/2011/12/06/2277838.html

主要是定义了一个hash，由于每一个状态只能用一个数组来表示，所以给每个状态都生成一个hash值，然后记忆化搜索

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

const int MAXN = 10;
const int MAXD = 50000;
const int HASH = 1000003;
int f[MAXD];
int g[MAXN][MAXN], heat[MAXN][MAXN];
int head[HASH], next[MAXD], e;
int st[MAXD][6];
int N, K;

int hash(int p[])
{
    int v = 0;
    for (int i = 0; i < 6; ++i)
        v = v * 10 + p[i];
    return (v & 0x7fffffff) % HASH;
}

void insert(int s)
{
    int h = hash(st[s]);
    next[e] = head[h];
    head[h] = e++;
}

int check(int s)
{
    int i, h = hash(st[s]);
    for (i = head[h]; i != -1; i = next[i])
        if (memcmp(st[i], st[s], sizeof(st[0])) == 0)
            break;
    return i;
}

int dp(int u)
{
    int k = check(u);
    if (k >= 0)
        return f[k];

    insert(u);

    int mm = INT_MAX;
    for (int i = 0; i < 6; ++i)
    {
        if (st[u][i])
            for (int j = 0; j < 6; ++j)
                if (st[u][j])
                {
                    if (i == j && st[u][j] < 2)
                        continue;
                    memcpy(st[e], st[u], sizeof(st[e]));
                    --st[e][i], --st[e][j], ++st[e][g[i][j]];
                    mm = min(mm, dp(e) + heat[i][j]);
                }
    }
    if (mm == INT_MAX)
        mm = 0;
    return f[u] = mm;
}

int main()
{
    int cases;
    scanf("%d", &cases);
    while (cases--)
    {
        scanf("%d", &N);

        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
            {
                int a, b;
                scanf("%d %d", &a, &b);
                g[i][j] = --a;
                heat[i][j] = b;
            }

        memset(head, -1, sizeof(head));
        memset(st[0], 0, sizeof(st[0]));
        scanf("%d", &K);
        for (int i = 0; i < K; ++i)
        {
            int a;
            scanf("%d", &a);
            ++st[0][--a];
        }
        e = 0;
        printf("%d\n", dp(e));

        char b[10];
        scanf("%s", b);
    }
    return 0;
}