2019 ICPC Asia Yinchuan Regional L. Xian Xiang

题意 n*m（n,m <= 7 )的图里边最多18个串 每个串长度不超过k (k <= 5)，每次选两个消除，类似连连看的方式，但是只能变一次方向，消除两个获得的价值是两个字符串位置一样的个数，假如 一共有 i 个，得到价值就是 s[i] (0 <= i <= k). 问消除所有的获得最大价值。

思路
状压dp，预处理一些东西，加速dp
算了复杂度感觉是 , 但实际可能有剪枝，达不到这个复杂度，莽一发过了。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;

char s[10][10][10];
int cnt;

struct node {
    int x, y;
}p[25];

int can[25][25][2], dp[N], val[25][25], a[15];


void solve(int j, int k) {
    int x1 = p[j].x, x2 = p[k].x; if(x1 > x2) swap(x1, x2);
    int y1 = p[j].y, y2 = p[k].y; if(y1 > y2) swap(y1, y2);
    int v1 = 0, v2 = 0;
    for(int i = 0; i < cnt; i++) {
        if(p[i].x == p[j].x && p[i].y >= y1 && p[i].y <= y2)
            v1 |= (1 << i);
        if(p[i].y == p[k].y && p[i].x >= x1 && p[i].x <= x2)
            v1 |= (1 << i);

        if(p[i].x == p[k].x && p[i].y >= y1 && p[i].y <= y2)
            v2 |= (1 << i);
        if(p[i].y == p[j].y && p[i].x >= x1 && p[i].x <= x2)
            v2 |= (1 << i);
    }
    v1 ^= (1 << j) | (1 << k);
    v2 ^= (1 << k) | (1 << j);
    can[j][k][0] = v1;
    can[j][k][1] = v2;
}
int T, n, m, k, all;
int get(int i, int j) {
    int num = 0;
    for(int h = 0; h < k; h++) {
        if(s[p[i].x][p[i].y][h] == s[p[j].x][p[j].y][h]) num++;
    }
    return num;

}

void init() {
    all = (1 << cnt) - 1;
    for(int i = 0; i < cnt; i++)
        for(int j = i + 1; j < cnt; j++) {
            solve(i, j);
            val[i][j] = a[get(i, j)];
        }

}

int main()
{
//#ifndef ONLINE_JUDGE
//    freopen("h.in", "r", stdin);
//#endif

    scanf("%d", &T);
    while(T--) {
        cnt = 0;
        scanf("%d %d %d", &n, &m, &k);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                scanf(" %s", s[i][j]);
                if(s[i][j][0] != '-') p[cnt++] = {i, j};
            }
        }
        for(int i = 0; i <= k; i++) scanf("%d", &a[i]);
        for(int sta = 0; sta < (1 << cnt); sta++) dp[sta] = -1e9;
        dp[0] = 0;
        init();
        for(int sta = 0; sta < (1 << cnt); sta++) {
            for(int i = 0; i < cnt; i++) {
                if(sta & (1 << i)) continue;
                for(int j = i + 1; j < cnt; j++) {
                    if(sta & (1 << j)) continue;
                    if((can[i][j][0] & sta) == can[i][j][0] || (can[i][j][1] & sta) == can[i][j][1])
                        dp[sta | (1 << i) | (1 << j)] = max(dp[sta | (1 << i) | (1 << j)], dp[sta] + val[i][j]);
                }
            }
        }
        printf("%d\n", dp[all]);
    }
    return 0;
}