d(i, j)表示使前i个数满足要求，而且第i个数值为j的最小改动次数。
d(i, j) = min{ d(i-1, k) | k == j | G[j][k] }
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 200 + 10; 7 8 int n, m, k; 9 int a[maxn]; 10 int d[maxn][maxn]; 11 bool G[maxn][maxn]; 12 13 int main() 14 { 15 int T; scanf("%d", &T); 16 while(T--) 17 { 18 scanf("%d%d", &n, &m); 19 memset(G, false, sizeof(G)); 20 while(m--) 21 { 22 int u, v; scanf("%d%d", &u, &v); 23 G[u][v] = G[v][u] = true; 24 } 25 scanf("%d", &k); 26 for(int i = 1; i <= k; i++) scanf("%d", a + i); 27 28 memset(d, 0x3f, sizeof(d)); 29 for(int i = 1; i <= k; i++) d[0][i] = 0; 30 for(int i = 1; i <= k; i++) 31 for(int j = 1; j <= n; j++) 32 for(int t = 1; t <= n; t++) if(G[j][t] || j == t) 33 d[i][j] = min(d[i][j], d[i-1][t] + (j == a[i] ? 0 : 1)); 34 35 int ans = k; 36 for(int i = 1; i <= n; i++) ans = min(ans, d[k][i]); 37 printf("%d ", ans); 38 } 39 40 return 0; 41 }