给我们n座房子，房子的高度各不相同， 从最低的房子开始， 每次跳到更高的房子， 跳n-1次最能跳到最高的房子了，但是每次跳跃的距离不能超过d
将这些房子在一维的方向上重新摆放（但是保持输入时的相对位置不变） ， 使得最矮的房子和最高的房子水平距离最大
将房子的坐标设为xi， n个变量， 和2(n-1)个约束关系， 典型的差分约束系统
高度相近的两个坐标（设为xi,xj)相减 abs(xi-xj) <= d, 要想办法去掉绝对值， 那么规定一律id大的减去id小的，那么结果就是正的
又需要保持输入的相对位置不变， 那么 x(i+1) - x(i) >=1, 因为要化为最短路 所以是 x(i) - x(i+1) <= -1
所以按照上面的分析构造图，然后跑一边最短路即可。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> #include <iostream> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <string> #include <math.h> using namespace std; #pragma warning(disable:4996) #pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; const int INF = 1 << 30; /* */ const int N = 1000 + 10; struct Node { int id, height; bool operator <(const Node &rhs) { return height < rhs.height; } }a[N]; struct Edge { int v, dist; Edge(){} Edge(int _v, int _dist) :v(_v), dist(_dist){} bool operator<(const Edge&rhs)const { return dist > rhs.dist; } }; vector<Edge> g[N]; int dist[N]; bool vis[N]; int dij(int x, int y, int n) { for (int i = 1; i <= n; ++i) dist[i] = INF; priority_queue<Edge> q; Edge cur, tmp; cur.dist = dist[x] = 0; cur.v = x; q.push(cur); while (!q.empty()) { cur = q.top(); q.pop(); int u = cur.v; if (dist[u] < cur.dist)//如果cur.dist < dist[u]， 那么可以继续更新其他顶点， 代替了条件vis[u] continue; for (int i = 0; i < g[u].size(); ++i) { int v = g[u][i].v; if (dist[v] > dist[u] + g[u][i].dist) { tmp.dist = dist[v] = dist[u]+ g[u][i].dist; tmp.v = v; q.push(tmp); } } } return dist[y]; } int spfa(int x, int y, int n) { for (int i = 1; i <= n; ++i) dist[i] = INF; queue<int> q; q.push(x); dist[x] = 0; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (int i = 0; i < g[u].size(); ++i) { int v = g[u][i].v; if (dist[v] > dist[u] + g[u][i].dist) { dist[v] = dist[u] + g[u][i].dist;//能更新就更新 if (!vis[v])//如果结点在队里里面，就不用重复入队了 { q.push(v); vis[v] = true; } } } } return dist[y]; } int main() { int n, d, t; scanf("%d", &t); for (int k = 1; k <= t; ++k) { scanf("%d%d", &n, &d); for (int i = 1; i <= n; ++i) g[i].clear(); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i].height); a[i].id = i; if (i != 1) g[i].push_back(Edge(i-1, -1)); } sort(a + 1, a + n + 1); bool flag = true; for (int i = 2; i <= n; ++i) { if (abs(a[i].id - a[i - 1].id) > d) { flag = false; break; } g[min(a[i].id, a[i - 1].id)].push_back(Edge(max(a[i].id, a[i - 1].id), d)); } printf("Case %d: ", k); if (!flag) puts("-1"); else { if (a[1].id > a[n].id) swap(a[1].id, a[n].id); printf("%d ", spfa(a[1].id, a[n].id,n)); } } return 0; }
用最短路求出解后， 其它点与源点的差值最大。
用最长路求出解后，其它点与源点的差值最小。