uva 1424 - Salesmen(dp)

题目链接：uva 1424 - Salesmen

题目大意：给定一个包含n个点的无向图和一个长度为L的序列A，要求修改尽量少得数，使得序列中的任意两个相邻数相等或者在途中相邻。

解题思路：dp[i][j]表示说长度为i且最后一个数为j的情况需要修改最少几次。dp[i][j] = min(dp[i][j], dp[i-1][k] + (j == A[i])?1:0));

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 105;
const int INF = 0x3f3f3f3f;

int n, m, k, g[N][N], A[2*N], dp[N*2][N];

void init () {
	int a, b;

	memset(g, 0, sizeof(g));
	memset(dp, INF, sizeof(dp));

	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) dp[0][i] = 0;
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		g[a][b] = g[b][a] = 1;
	}

	scanf("%d",  &k);
	for (int i = 1; i <= k; i++) scanf("%d", &A[i]);
}

int solve() {
	int ans = k;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
			for (int t = 1; t <= n; t++) if (j == t || g[j][t]) {
				dp[i][j] = min(dp[i][j], dp[i-1][t]+(j == A[i] ? 0 : 1));
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		ans = min(dp[k][i], ans);
	}
	return ans;
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init();	
		printf("%d\n", solve());
	}
	return 0;
}