제목: n (n < = 100) 개의 점을 포함하는 무방향 연결도와 L 길이의 시퀀스 A (L < = 200) 를 지정합니다. 시퀀스에 있는 임의의 두 개의 인접수가 같거나 그림에 있는 두 개의 인접 노드를 수정하는 것이 임무입니다.
사고방식: dp[i][j]로 1부터 위치까지 i가 j로 끝나는 최소 수정수를 표시하면 답은max(dp[L][1~n])이다.
만약 a[i]=j, dp[i][j]=min(dp[i-1][j], dp[i-1][k])이라면.그렇지 않으면 dp[i][j]=min(dp[i-1][j]+1, dp[i-1][k]+1)j와 k는 인접 노드이다.
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 21e2 + 10;
const int maxt = 100200;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-8;
typedef long long ll;
vector g[110];
int dp[210][110];
int a[220];
void init(){
for(int i = 1; i <= 100; ++i) g[i].clear();
memset(dp, INF, sizeof dp);
}
int main(){
int T;
scanf("%d", &T);
while(T--){
int n, m;
init();
scanf("%d%d", &n, &m);
for(int i = 0; i < m; ++i){
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
int l;
scanf("%d", &l);
for(int i = 1; i <= l; ++i)
scanf("%d", &a[i]);
dp[1][a[1]] = 0;
for(int i = 2; i <= l; ++i){
for(int j = 1; j <= n; ++j){
if(j == a[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j] + 1;
for(int k = 0; k < g[j].size(); ++k){
int u = g[j][k];
if(j == a[i])
dp[i][j] = min(dp[i][j], dp[i - 1][u]);
else
dp[i][j] = min(dp[i][j], dp[i - 1][u] + 1);
}
}
}
int ans = INF;
for(int i = 1; i <= n; ++i) ans = min(ans, dp[l][i]);
printf("%d
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)
의 해설 기사입니다.
해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다.
※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다.
문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
