本文共 762 字，大约阅读时间需要 2 分钟。
题意：
给一个n个点m条边的有向无环图，再给一个长度L的序列A，然后求图中的一条长度为L的路径B（这条路径的同一个点可以连续重复出现多次）
问路径B和序列A不相等的数最少多少， 即Ai != Bi, 0<=i<L的数。
思路：
刚看这题，就觉得像树形dp，最终做出来不像树形dp。。
f[i][j]表示i点，在路径序列的前j点中的最小距离。 那么 j=0, f[u][0] = d(u, arr[0]); j>0, f[u][j] = min(f[u][j], f[v][j-1]+d(u, arr[j])), v是与u相邻的点f[u][j] = min(f[u][j], f[u][i-1]+d(u,arr[i])); //取重复当前点的情况
代码：
#include#include #include #include #include #include using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f;const int MAXN = 210;int n, m, len,ans,arr[MAXN];bool vis[MAXN];int f[MAXN][MAXN];vector adj[MAXN];inline int d(int a, int b){ if(a==b) return 0; else return 1;}int main(){ int T; scanf("%d", &T); while(T--){ scanf("%d%d", &n, &m); for(int i=0; i
转载地址：http://xvzni.baihongyu.com/