題意:一個n個點的聯通圖(n<=100)的無向聯通圖，還有一個長度為L序列(L<200)，問最少改變序列中幾個數使得序列相鄰兩個數是相同或者在圖中相鄰

題解:dp[i][j]代表第i個數變為j的最小次數,O(n*L*n)

#include <bits/stdc++.h> #define maxn 210 #define INF 0x3f3f3f3f typedef long long ll; using namespace std; int g[maxn][maxn], a[2*maxn], dp[maxn][maxn]; int main(){int n, m, t, b, ans, c, T;scanf("%d", &T);while(T--){ans = INF;memset(dp, INF, sizeof(dp));memset(g, 0, sizeof(g));scanf("%d%d", &n, &m);for(int i=0;i<m;i++){scanf("%d%d", &b, &c);g[b][c] = g[c][b] = 1;}for(int i=1;i<=n;i++) g[i][i] = 1;scanf("%d", &t);for(int i=1;i<=t;i++)scanf("%d", &a[i]);for(int i=1;i<=n;i++) dp[1][i] = (i==a[1])?0:1;for(int i=2;i<=t;i++){for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){if(g[j][k] == 1){dp[i][j] = min(dp[i][j], dp[i-1][k]+((j==a[i])?0:1));}}}}for(int i=1;i<=n;i++)ans = min(ans, dp[t][i]);printf("%d\n", ans);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/Noevon/p/7645631.html

總結

以上是生活随笔為你收集整理的UVALive4256 Salesmen的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。