uva 1424 (dp 전문 그룹 G 문제)
제목
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;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
