题意:给定一个包含n个点的无向连通图和一个长为L的序列,你的任务是修改尽量少的点
,使得序列中的任意两个相邻的数或者相同,或者相邻
思路:不算太难想到的DP。dp[i][j]表示第i个是j 的最少的修改数,然后每次都枚举它的相邻点,所以dp[i][j]=min(dp[i][j],dp[i-1][k])
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int MAXN = 1005; int a[MAXN],n,m,num; int dp[MAXN][MAXN]; vector<int> arr[MAXN]; int main(){ int t; scanf("%d",&t); while (t--){ scanf("%d%d",&n,&m); for (int i = 1; i<= n; i++) arr[i].clear(),arr[i].push_back(i); for (int i = 1; i <= m; i++){ int u,v; scanf("%d%d",&u,&v); arr[u].push_back(v); arr[v].push_back(u); } scanf("%d",&num); memset(dp,0x3f3f3f3f,sizeof(dp)); for (int i = 1; i <= num; i++) scanf("%d",&a[i]); for (int i = 1; i <= n; i++){ if (i == a[1]) dp[1][i] = 0; else dp[1][i] = 1; } for (int i = 2; i <= num; i++){ for (int j = 1; j <= n; j++){ int len = arr[j].size(); for (int k = 0; k < len; k++){ int temp = arr[j][k]; dp[i][j] = min(dp[i][j],dp[i-1][temp]); } if (j != a[i]) dp[i][j]++; } } int Min = 0x3f3f3f3f; for (int i = 1; i <= n; i++) Min = min(Min,dp[num][i]); printf("%d\n",Min); } return 0; }