JZOJ 1303 骑士

题意太杀了，而且根本没法往状压 DP 方面想……

首先，补充题意：同一时刻只能移动一个骑士！
第二，八方移动下，两点最短路是切比雪夫距离。

考虑到骑士间互不干涉，可以对于每个骑士独立地计算再合并。
（如果有别的骑士挡路可以直接避开，其他避不开的肯定不是最优解。）

骑士仅会停留在初始位置或是某个人质的位置。
设 fi,S,j 表示第 i 个骑士俘获的人质构成 S 集合，最后俘获的是 j。
转移时，枚举 i,S,j 和将要俘获的人质 k，那么有转移： fi,S⋃{k},k=minfi,S,j+dis(pj,pk)

其中 pi 表示第 i 个人质的坐标，dis(x,y) 表示 x,y 的切比雪夫距离。

然后考虑合并答案，设 gi,S 表示前 i 个骑士共拯救了集合 S 内的人质。
枚举 i,S 和这个骑士俘获的人质 S′⊆S 和他最后俘获的人质 j。
有 gi,S=mingi−1,S−S′+fi,S′,j

注意一些初值。

代码：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define dis(x1,y1,x2,y2) (max(abs((x1) - (x2)),abs((y1) - (y2))))
using namespace std;
const int N = 10;
const int W = 8;
int T;
int n,m,full;
int K[N + 5][2],P[N + 5][2];
int f[N + 5][(1 << N) + 5][N + 5];
int g[N + 5][(1 << N) + 5];
int ans;
char s[W + 5][W + 5];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        n = m = 0,memset(f,0x3f,sizeof f),memset(g,0x3f,sizeof g),g[0][0] = 0,ans = 0x3f3f3f3f;
        for(register int i = 1;i <= W;++i)
        {
            scanf("%s",s[i] + 1);
            for(register int j = 1;j <= W;++j)
                if(s[i][j] == 'K')
                    K[++n][0] = i,K[n][1] = j;
                else if(s[i][j] == 'P')
                    P[++m][0] = i,P[m][1] = j;
        }
        for(register int i = 1;i <= n;++i)
            for(register int j = 1;j <= m;++j)
                f[i][1 << j - 1][j] = dis(K[i][0],K[i][1],P[j][0],P[j][1]);
        full = (1 << m) - 1;
        for(register int i = 1;i <= n;++i)
            for(register int j = 0;j <= full;++j)
                for(register int k = 1;k <= m;++k)
                    if(!(j & (1 << k - 1)))
                        for(register int l = 1;l <= m;++l)
                            if(j & (1 << l - 1))
                                f[i][j | (1 << k - 1)][k] = min(f[i][j | (1 << k - 1)][k],f[i][j][l] + dis(P[l][0],P[l][1],P[k][0],P[k][1]));
        for(register int i = 1;i <= n;++i)
            for(register int j = 0;j <= full;++j)
            {
                g[i][j] = g[i - 1][j];
                for(register int k = 0;k <= j;++k)
                    if((k & j) == k)
                        for(register int l = 1;l <= m;++l)
                            if(k & (1 << l - 1))
                                g[i][j] = min(g[i][j],g[i - 1][j ^ k] + f[i][k][l]);
            }
        printf("%d\n",g[n][full]);
    }
}