uva 1424 (dp 전문 그룹 G 문제)

링크:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36240
제목
n (n < = 100) 개의 점 을 포함 하 는 무방 향 연통 도와 길이 가 L 인 서열 A (L < = 200) 를 지정 합 니 다. 당신 의 임 무 는 가능 한 한 적은 수 를 수정 하여 서열 에 있 는 임의의 두 개의 인접 한 수 나 같 거나 그림 에 있 는 두 개의 인접 한 결점 을 수정 하 는 것 입 니 다.
문제 풀이:
행렬 a 로 그림 을 저장 합 니 다. 만약 i, j 사이 에 a [i] [j] = a [j] [i] = 1 이 있 으 면 정사각선 도 1 로 설정 하고 점 과 그 자체 의 연결선 과 같 습 니 다.
주어진 시퀀스 A 를 배열 f 로 저장 합 니 다.
dp [i] [k] 로 i 위 가 k 일 때 수정 해 야 할 최소 횟수 를 표시 합 니 다.
dp [0] [i] = (f [i]! = i) 를 알 수 있 습 니 다.
동적 이동 방정식 은 dp [i] [k] = min (dp [i] [k], dp [i - 1] [j] + f [i]! = k) 이다.그 중에서 j 는 1 ~ n1 의 모든 a [j] [k] = 1 의 값 이다.
마지막 으로 dp [n - 1] [i] (1 < = i < = n1) 의 최소 값 은 바로 원 하 는 것 입 니 다.
이 문제 의 잘못된 점: (내 것)
경계 범위 에 주의해 야 한다.
코드 는 다음 과 같 습 니 다:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int INF = 0x3f3f3f3f;
int a[maxn][maxn];
int d[2*maxn][maxn];
int f[2*maxn];

int main(){
    int T;
    cin>>T;
    while(T--){
        int n1,n2;
        cin>>n1>>n2;
        memset(a,0,sizeof(a));
        for(int i = 1;i<=n1;i++)a[i][i] = 1;
        for(int i= 0;i<n2;i++){
            int x,y;
            cin>>x>>y;
            a[x][y] = a[y][x] = 1;
        }
        int n;
        cin>>n;
        memset(d,INF,sizeof(d));
        for(int i = 0;i<n;i++)cin>>f[i];
        for(int i = 1;i<=n1;i++)d[0][i] = (f[0] != i);
        for(int i = 1;i<n;i++){
            for(int k = 1;k<=n1;k++){
                for(int j = 1;j<=n1;j++){
                    if(a[k][j]){
                        d[i][k] = min(d[i][k],d[i-1][j]+(f[i]!=k));
                    }
                }
//                cout<<i<<" "<<k<<" "<<d[i][k]<<endl;
            }
        }
        int ans = INF;
        for(int i = 1;i<=n1;i++){
            ans = min(ans,d[n-1][i]);
        }
        cout<<ans<<endl;
    }
}