UVALive 4256 Salesmen 【簡單dp】

題意：給你一棵樹，和一串序列，求最少改變多少個數使得序列中的每個相鄰的數要麼相等要麼在樹上相鄰。

分析：設狀态dp[i][j]表示長度為i以j結尾最少修改幾次合法。

轉移dp[i][k]=min(dp[i][k],dp[i-1][j]+(a[i]!=k))  k是目前最後數字，j是k前一個，j可以等于k（處理與前面相等），若j與k在樹上相鄰，判斷a[i]!=k,dp[i][k]+1;

代碼：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define Mn 105
#define Mm 200
#define mod 1000000007
#define CLR(a,b) memset((a),(b),sizeof((a)))
#define CPY(a,b) memcpy ((a), (b), sizeof((a)))
#pragma comment(linker, "/STACK:102400000,102400000")
#define ul u<<1
#define ur (u<<1)|1
using namespace std;
typedef long long ll;
int a[Mm];
int dp[Mm][Mn];
int g[Mn][Mn];
int main() {
    int n,m,t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        CLR(g,0);
        while(m--) {
            int u,v;
            scanf("%d%d",&u,&v);
            g[u][v]=g[v][u]=1;
        }
        scanf("%d",&m);
        for(int i=1;i<=m;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) g[i][i]=1;
        for(int i=1;i<=m;i++) {
            for(int j=1;j<=n;j++) dp[i][j]=INF;
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    if(g[j][k]) dp[i][k]=min(dp[i][k],dp[i-1][j]+(a[i]!=k));
        }
        int ans=m;
        for(int i=1;i<=n;i++) ans=min(dp[m][i],ans);
        printf("%d\n",ans);
    }
    return 0;
}