差束约分
题意：有n个屋子，超人从最矮的屋子开始，依次跳下比当前屋子高且最接近当前高度的屋子（即按照屋子高度增序来跳），但超人跳跃还有一个水平距离限制D，他每次跳的水平距离<=D。现在给你每个屋子的高度是它们的相对位置，你不能改变屋子的相对位置，但是可以水平移动屋子，使得最矮的屋子和最高的屋子的水平距离最大。如果无论怎样移动，超人都无法跳到最后那个屋子则输出-1
这题是个差束约分
看sample说明问题
sample3
4 2
10 20 16 13
超人从10开始，跳到13，但是10和13的水平距离至少为3，但超人的水平限制距离是2，所以无论怎么移动都无法跳过去，输出-1
看sample1
4 4
20 30 10 40
我们先给这些屋子，按横坐标给他们标号
20(1) 30(2) 10(3) 40(4)
所以我们可以描述为，超人跳跃的顺序为3 --->1---->2---->4，那么我们要求的就是3号点和4号点的最远距离（前提是要保证超人能完成整个跳跃）
另外超人的跳跃是按照高度来的，所以超人跳跃的路径其实是唯一确定的。要超人完成整个跳跃，就要保证超人能从“当前点”跳向“下一个点”，所以两点的水平距离有一个限制
| "下一个点的坐标" - “当前点的坐标” | <= lim ,这里有一个绝对值，因为表示的是距离，所以我们可以约定一下，消去绝对值
d[v] <= d[u]+lim ，其中点v的坐标大于点u的坐标
再看sample1:
要从10(3)跳到20(1)
| 点3的坐标 - 点1的坐标| <= lim ，约定为 d[3] - d[1] <= lim ----> d[3] <= d[1] + lim ---->因而建立的有向边为 <1,3> , w = lim
要从30(2)跳到40(4)
|点2的坐标 - 点4的坐标| <= lim , 约定为 d[4] - d[2] <= lim ----> d[4] <= d[2] + lim ----->因而建立有向边<2,4> , w = lim
另外还别漏了一点，对于相邻的两个点，它们的距离至少为1
例如
30(2) 10(3)
这两个点要满足 d[3] - d[2] >= 1 ---> d[2] - d[3] <= -1 ---> d[2] <= d[3] + (-1) ----> 建立有向边 <3,2> , w = -1
这样就建立了图，例如sample，我们就是要求点3到点4的最短路
还注意一点，因为我们建图的时候是约定好的，有向边都是 标号小的点 ---> 标号大的点（除开边权为-1的边），所以我们找最短路的时候也要约定从标号小的点 到 标号大的点
如果 起点标号 > 终点标号 ， 则反过来求最短路
#include <cstdio> #include <cstring> #include <vector> #include <stack> #include <queue> #include <algorithm> using namespace std; #define N 1010 #define INF 0x3f3f3f3f #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) struct edge{ int v,w,next; }; struct node{ int h,pos; }; int n,lim; vector<struct edge>e[N]; struct node a[N]; int Abs(int a) { return a>0?a:-a; } int cmp(struct node x ,struct node y) { return x.h < y.h; } void add(int u ,int v , int w) { struct edge temp; temp.v = v; temp.w = w; e[u].push_back(temp); } int build() { int ok = 1; sort(a+1,a+n+1,cmp); for(int i=1; i<=n; i++) e[i].clear(); for(int i=1; i<n; i++) { add(i+1 , i , -1); int u = min(a[i].pos , a[i+1].pos); int v = max(a[i].pos , a[i+1].pos); int w = Abs(a[i].pos - a[i+1].pos); if(w > lim) return 0; add(u, v, lim); } return 1; } void spfa(int s , int t) { stack<int>sta; int cc[N]; int d[N]; bool ins[N]; memset(d,0x3f,sizeof(d)); memset(ins,false,sizeof(ins)); memset(cc,0,sizeof(cc)); while(!sta.empty()) sta.pop(); d[s] = 0; ins[s] = true; sta.push(s); cc[s]++; while(!sta.empty()) { int u = sta.top(); int size = e[u].size(); sta.pop(); ins[u] = false; for(int i=0; i<size; i++) { struct edge temp = e[u][i]; int v = temp.v; int w = temp.w; if(d[u] + w < d[v]) { d[v] = d[u] + w; if(!ins[v]) { cc[v]++; ins[v] = true; sta.push(v); if(cc[v] > n) { printf("-1\n"); return ; } } } } } printf("%d\n",d[t]); } int main() { int T; scanf("%d",&T); for(int cas=1; cas<=T; cas++) { scanf("%d%d",&n,&lim); for(int i=1; i<=n; i++) { scanf("%d",&a[i].h); a[i].pos = i; } printf("Case %d: ",cas); if(!build()) { printf("-1\n"); continue; } int u = min(a[1].pos , a[n].pos); int v = max(a[1].pos , a[n].pos); spfa(u,v); } return 0; }