. . 题意：有n棵树依次排列，忍者要从最矮的树开始跳，从矮到高跳完所有树，忍者跳跃的距离不超过k，问最矮的树和最高的数之间最远的距离是多少，如果无解输出-1 . . 解法：查分约束，对于第i棵树以及第i+1棵树，保证前面的树在前，即距离dist[i]-dist[i+1]<0，查分约束要等于，所以i和i+1连一条权为-1的边。假设高度排i的树为Xi，那么有 abs(dist[Xi]-dist[X(i+1)]) <= k，所以连一条长度为k的边（或者你可以判断谁前谁后），然后跑一遍spfa就可以了。注意如果矮的树在高的树后面，得到的结果会是负数，所以对于这种情况可以把整个序列倒过来跑。 . .
#include <iostream> #include <string> #include <string.h> #include <stdlib.h> using namespace std; const int maxn = 3000; const int all = 3000000; int a[maxn], b[maxn]; int dist[maxn], n, d[all], m; int tar[maxn], val[maxn], nextt[maxn], last[maxn], tot, ans, s, t; int tong[1000010]; bool flag[maxn]; void insert(int x, int y, int z) { tot++; tar[tot] = y; val[tot] = z; nextt[tot] = last[x]; last[x] = tot; } int spfa() { int sum[maxn] = {0}; dist[b[n]] = 0; d[1] = b[n]; int i = 0, j = 1; memset(flag, 0, sizeof(flag)); flag[b[n]] = true; sum[b[n]] = 1; while (i != j) { i++; if (i>all) i = 1; int k = last[d[i]]; while (k != 0) { if (dist[d[i]]+val[k] < dist[tar[k]]) { dist[tar[k]] = dist[d[i]]+val[k]; if (!flag[tar[k]]) { flag[tar[k]] = true; j++; if (j > all) j = 1; d[j] = tar[k]; } sum[tar[k]]++; if (sum[tar[k]] > n) return -1; } k = nextt[k]; } flag[d[i]] = false; } return dist[b[1]]; } int main() { // while (scanf("%d %d", &n, &m) != EOF) { if (n == 0 && m == 0) break; tot = 0; memset(last, 0, sizeof(last)); memset(tong, 0, sizeof(tong)); ans = -1; for (int i = 1; i <= n; i++) { cin >> a[i]; tong[a[i]] = i; } int sum = 0; for (int i= 1; i <= 1000000; i++) if (tong[i] != 0) { sum++; a[tong[i]] = sum; if (sum == 1) s = tong[i]; if (sum == n) t = tong[i]; } if (s > t) { for (int i = 1; i <= n/2; i++) swap(a[i], a[n-i+1]); } for (int i = 1; i <= n; i++) b[a[i]] = i; bool fuck = false; for (int i = 1; i < n; i++) if (abs(b[i+1]-b[i]) > m) fuck = true; if (fuck) {cout << -1 << endl; continue;} for (int i = 1; i < n; i++) insert(i, i+1, -1); for (int i = 1; i < n; i++) { insert(b[i+1], b[i], m); insert(b[i], b[i+1], m); } for (int i = 1; i <= n; i++) dist[i] = n*m+1; int ans = spfa(); if (ans < 0) cout << -1 << endl; else cout << ans << endl; } }