自己没有把题目看好，，以为是要让图对应序列。。
其实是让序列对应图，，
那么确实比较好做。。
然而还是 要想到 因为dp n n1 不大 所以可以用两维 然后就像是暴力枚举一样。。
#include<bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)); #define sf scanf #define pf printf #define bug1 printf("bug1\n"); #define N 105 #define M 10 #define INF 1e9 #define LL long long #define inf 0x3f3f3f3f int n1,n2,n; int dp[2*N][N]; vector<int>arr[N]; int a[2*N]; int main(){ int T; sf("%d",&T); while(T--){ int ans=INF; sf("%d%d",&n1,&n2); for(int i=1;i<=n1;++i){ arr[i].clear();arr[i].push_back(i);//别人的这个地方挺巧的，自然就给自己加上了边 } for(int i=1;i<=n2;++i){ int u,v; sf("%d%d",&u,&v); arr[u].push_back(v); arr[v].push_back(u); } sf("%d",&n); for(int i=1;i<=n;++i){ sf("%d",&a[i]); } mem(dp,inf); for(int i=1;i<=n1;++i){ if(i==a[1])dp[1][i]=0; else dp[1][i]=1; } for(int i=2;i<=n;++i){// for(int j=1;j<=n1;++j){//下一个节点改为j， for(int k=0;k<arr[j].size();++k){ int tmp=arr[j][k]; dp[i][j]=min(dp[i][j],dp[i-1][tmp]); //自己有点想错了，，我的是要让第i个为j，那么就是要改的，就要+1 }//你回去找 if(j!=a[i])dp[i][j]++; } } for(int i=1;i<=n1;++i){ ans=min(ans,dp[n][i]); } pf("%d\n",ans); } }
