uvalive4256

제목 대의: 무방향 연결도와 일련의 숫자를 제시한 다음에 이 숫자가 무방향 연결도에서 연결되거나 서로 같도록 수정해 달라고 한다.
아이디어: DP.dp[i][j]는 1부터 i까지의 숫자를 j로 끝내려면 몇 개의 숫자를 수정해야 하는지를 나타낸다.dp[i][j]=min(dp[i][j], dp[i-1][k]+(j=x?0:1))에서 x는 주어진 서열 중 i번째 위치의 숫자가 얼마인지를 나타낸다.이 상태 전이 방정식의 전제는 j와 k가 반드시 연결되어야 한다는 것이다.
코드:

#include 
using namespace std;
#include 
#include 

const int INF = 0x3f3f3f3f;
const int maxn = 1010;

int dp[maxn][maxn];
int map[maxn][maxn];
int num[maxn];

int main() {
    int kase;
    scanf("%d",&kase);
    while(kase--) {
        int n,m,len;
        scanf("%d %d",&n,&m);
        memset(map,0,sizeof(map));
        for(int i = 1; i <= n; i++)
            map[i][i] = 1;
        int u,v;
        for(int i = 0; i < m ; i++) {
            scanf("%d %d",&u,&v);
            map[u][v] = 1;
            map[v][u] = 1;
        }
        scanf("%d",&len);
        for(int i = 0; i < len; i++)
            scanf("%d",&num[i]);
        for(int i = 0; i < len;i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = INF;
        for(int i = 1; i <= n; i++)
            dp[0][i] = 1;
        dp[0][num[0]] = 0;
        for(int i = 1; i < len; i++) {
            int x = num[i];
            for(int j  = 1; j <= n; j++) {
                for(int k = 1; k <= n; k++) 
                    if(map[j][k] == 1) 
                        dp[i][j] = min(dp[i][j],dp[i - 1][k] + (j == x ?0:1));
            }dp[i][j] = min(dp[i][j],dp[i - 1][k] + (j == x ?0:1));
            }

        }
        int ans = INF;
        for(int i = 1; i <= n; i++)
            ans = min(ans,dp[len - 1][i]);
        printf("%d
",ans);
    }
    return 0;
}