作者:desn | 来源:互联网 | 2023-12-14 11:49
本文讨论了使用差分约束系统求解HouseMan跳跃问题的思路与方法。给定一组不同高度,要求从最低点跳跃到最高点,每次跳跃的距离不超过D,并且不能改变给定的顺序。通过建立差分约束系统,将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法,并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。
题意:给个n个不同的高度,一个人从最低点跳跃,每次可以跳到第一个比它高的位置,最后跳到最高点,然后每次最多可以跳的距离为D,而且在跳跃时可以在不改变给定顺序的情况下移动这些高度,使得最后起始点和终点的位置最远,
思路:自己想了一会,想的方向错了,我自己想的方法是将最小高度记为0,最大高度记为n-1,然后写查分约束方程,这了一会发现条件不足,没想法了,看了大牛们的解法发现原来以给定的顺序直接进行条件就可以了,而且好简单,因为我们不能调整给定的顺序,那么对于给定的顺序就可以有pos(i+1)>=pos(i)+1,那么可以写出一个条件就是i+1–>i连一条权值为-1的边,还有一个条件是相邻两个要跳跃的距离不可以大于D,可以写出另一个方程,而现在条件全部是基于给定的序列,那么剩下的条件也要在这个基础进行,右面的点一定是在左边的点的后面,那么式子也就很好列出来了,图建完了,查询距离就用SPFA判环并输出就行了,有一点小问题就是建边的方向和跳跃的方向不同,我们要保证是向一个方向建图的,为什么这样呢,比如举个栗子,与例1类似,4 4,10 30 20 40这组的话10到20,跳跃的顺序是10 20 30 40,但是如果也是按照这个顺序建边的话,那么你将无法知道10的右面是谁到底是20还是30,找不到既定的顺序,所以只能这样建边,那么随之而来的问题就是,1和n的位置关系,如果1在n的左面那么肯定是从1到n跑spfa,因为我是从左到右建边的,1在n右面的话,也就是从n到1跑最短路了,这块要注意一下
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1010;
const int INF=0x3f3f3f3f;
struct sa
{
int val;
int id;
} a[maxn];
int cmp(sa x,sa y)
{
return x.valstruct EdgeNode
{
int to;
int w;
int next;
};
EdgeNode edges[maxn*maxn];
int N,M;
int head[maxn],edge;
bool vis[maxn];
queue<int>que;
int dis[maxn],cnt[maxn];
void addedge(int u,int v,int c)
{
edges[edge].w=c;
edges[edge].to=v;
edges[edge].next=head[u];
head[u]=edge++;
}
void init()
{
memset(a,0,sizeof(a));
memset(cnt,0,sizeof(cnt));
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
memset(head,-1,sizeof(head));
edge=0;
}
bool spfa(int s,int n)
{
int u;
for(int i=0; i<=n; i++)
dis[i]=INF;
memset(vis,0,sizeof(vis));
while(!que.empty())
que.pop();
que.push(s);
vis[s]=true;
dis[s]=0;
memset(cnt,0,sizeof(cnt));
cnt[s]=1;
while(!que.empty())
{
u=que.front();
que.pop();
vis[u]=false;
for(int i=head[u]; i!=-1; i=edges[i].next)
{
int v=edges[i].to;
int w=edges[i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if(!vis[v])
{
vis[v]=true;
que.push(v);
if(++cnt[v]>=n)
return false;
}
}
}
}
return true;
}
int main()
{
int T,n,d;
cin>>T;
int Case=0;
while(T--)
{
init();
cin>>n>>d;
for(int i=1; i<=n; i++)
{
cin>>a[i].val;
a[i].id=i;
}
for(int i=1;i1,i,-1);
sort(a+1,a+1+n,cmp);
for(int i=1; i