b站看到的有意思的问题

5月11日的时候在 b 站看了一个最长手势密码的问题，觉得挺有意思，恰好当时学了状压 dp 就试着写了写

[ᴠɪᴏʟᴇᴛᴏᴀsᴛ]
看到这个问题的时候dna就动了，刚好最近在学壮压dp，就自己出题试试写了写，可惜这种方法因为空间不能求5以上的方格，最后两张图分别是3和4的时候的答案，回溯输出路径写了好久，以不同起点怎么求也想了半天，到时候我能给新生出题的时候狠狠的折磨他们

#include<bits/stdc++.h>
using namespace std;
const int N=17,M=1<<N;
double f[M][N];
double w[N*3][N*3];
int main()
{
    ios::sync_with_stdio(0),cout.tie(0),cout.tie(0);
    int n;cin>>n;
    int nn=n*n;//点的个数
    for(int i=0;i<n*n;++i)
    {
        for(int j=0;j<n*n;++j)
        {
            w[i][j]=w[i+nn][j]=w[i][j+nn]=sqrt((j%n-i%n)*(j%n-i%n)+(j/n-i/n)*(j/n-i/n));
            //存下每个点为到其他点的距离，不同起点p只需在用的 w 时 w[i+p][j+p]即可
        }
    }
        memset(f,0,sizeof f);
        for(int k=0;k<1<<nn;++k)//枚举状态
        {
            for(int i=0;i<nn;++i)
            {
                if(k>>i&1)
                {
                    for(int j=0;j<nn;++j)
                    {
                        if(i!=j&&(k-(1<<i))>>j&1)
                        {
                            f[k][i]=max(f[k-(1<<i)][j]+w[i][j],f[k][i]);
                        }
                    }
                }
            }
        }
        double mx=0;int p=0;
        for(int i=0;i<nn;++i)
        {
            if(f[(1<<nn)-1][i]>mx)
            {
                mx=f[(1<<nn)-1][i];
                p=i;
            }
        }
        memset(f,0,sizeof f);
        for(int k=0;k<1<<nn;++k)
        {
            for(int i=0;i<nn;++i)
            {
                if(k>>i&1)
                {
                    for(int j=0;j<nn;++j)
                    {
                        if(i!=j&&(k-(1<<i))>>j&1)
                        {
                            f[k][i]=max(f[k-(1<<i)][j]+w[i+p][j+p],f[k][i]);
                        }
                    }
                }
            }
        }
        int pp;mx=0;
        for(int i=0;i<nn;++i)
        {
            if(f[(1<<nn)-1][i]>mx)
            {
                mx=f[(1<<nn)-1][i];
                pp=i;
            }
        }
        cout<<mx<<'\n';
        double res=mx;
        int i=pp;
        int k=(1<<nn)-1;
        while(fabs(res)>1e-6)
        {
            for(int j=nn-1;j>=0;--j)
            {
                if((k-(1<<i))>>j&1 && fabs(res-f[k-(1<<i)][j]-w[i+p][j+p])<1e-6)
                {
                            cout<<(i+p)%nn+1<<' ';
                            res-=w[i+p][j+p];
                            k=k-(1<<i);
                            i=j;
                }
            }
        }
        cout<<(i+p)%nn+1;
}