UVALive4256[Salesmen] 动态规划

题目链接

---

题目大意：给出一张图，然后给出一个序列，修改序列中一些数字，要求使这个序列相邻的两个点．要么是相同的点，要么在图中是相邻点；

---

解题报告：

：dp[i][j]表示序列前i个数以j结尾需要修改的最小个数

dp[i][j]=min( dp[i-1][k] + (j==a[i])?0:1 ) k和j连通或相同

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;
#define Inf 0x3f3f3f3f
vector<int> G[maxn];

int A[maxn*2], dp[maxn*2][maxn];

int main(){
    int T;
    scanf("%d", &T );
    while( T-- ) {
        int n, m, l;
        scanf("%d%d", &n, &m );
        for ( int i=1; i<=n; i++ ) G[i].clear();
        for ( int i=1; i<=n; i++ ) G[i].push_back(i);
        for ( int i=1; i<=m; i++ ){
            int x, y;
            scanf("%d%d", &x, &y );
            G[y].push_back(x);
            G[x].push_back(y);
        }
        scanf("%d", &l );
        for ( int i=1; i<=l; i++ ) scanf("%d", &A[i] );
        for ( int i=1; i<=l; i++ )
            for ( int j=1; j<=n; j++ ){
                dp[i][j]=Inf;
                for ( int k=0; k<G[j].size(); k++ ){
                    if( j==A[i] )
                        dp[i][j]=min(dp[i][j], dp[i-1][G[j][k]] );
                    else 
                        dp[i][j]=min(dp[i][j], dp[i-1][G[j][k]]+1 );
                }
            }
        int ans=Inf;
        for ( int i=1; i<=n; i++ ) ans=min(ans, dp[l][i]);
        printf("%d\n", ans);
    }
    return 0;
}