LA 4256 商人

题目链接：https://vjudge.net/contest/160916#problem/B

题意：给一个无向图，和一个序列；要求，在这个序列中，两两相连的两个数相同，或者，在无向图中相邻；（n<=200）

分析：

d[i][j] 前 I 个数，最后一位是 j 时，最少的改动量；

我的渣的地方，就是，相同的时候，前面那个和我要改动的相同；

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int inf = 0x3f3f3f3f;

 bool maps[maxn][maxn];

 int d[maxn][maxn];

 int a[maxn];

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         int n,m;

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

         memset(maps,,sizeof(maps));

         memset(d,inf,sizeof(d));

         for(int i=; i<m; i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             maps[u][v] = maps[v][u] = ;

         }

         int k;

         scanf("%d",&k);

         for(int i=; i<=k; i++)

             scanf("%d",&a[i]);

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

         {

             d[][i] = ;

         }

         d[][a[]] = ;

         int ans = inf;

         for(int i=; i<=k; i++) //长度

         {

             for(int j=; j<=n; j++) //d[i][j]最后面是j

             {

                 int cast = j==a[i] ? :;

                 for(int m=; m<=n; m++) //枚举前面那个数

                 {

                     if(maps[j][m]||j==m)

                         d[i][j] = min(d[i][j],d[i-][m]+cast);

                     if(i==k)

                         ans = min(ans,d[i][j]);

                 }

             }

         }

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

     }

     return ;

 }