热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

差分约束系统求解HouseMan跳跃问题的思路与方法

本文讨论了使用差分约束系统求解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//addedge(i+1,i,-1);
            if(a[i].id1].id)
                addedge(a[i].id,a[i+1].id,d);
            else
                addedge(a[i+1].id,a[i].id,d);//只能从一个方向往另一个方向加边
        }
        cout<<"Case "<<++Case<<": ";
        bool flag=1;
        int first, second;

        if(a[1].id1].id;
            secOnd=a[n].id;
        }
        else
           {
               first=a[n].id;
               secOnd=a[1].id;
           }
           flag=spfa(first,n);
        if(flag==false)
            cout<<-1<else
        {
            cout<//这里要输出的是n到1的距离,但是second不能换成n,因为排过序了,n不一定是原来的顺序,所以要用id,这块也要注意一下
        }
    }
    return 0;
}

推荐阅读
  • 单链表的高效遍历及性能优化策略
    本文探讨了单链表的高效遍历方法及其性能优化策略。在单链表的数据结构中,插入操作的时间复杂度为O(n),而遍历操作的时间复杂度为O(n^2)。通过在 `LinkList.h` 和 `main.cpp` 文件中对单链表进行封装,我们实现了创建和销毁功能的优化,提高了单链表的使用效率。此外,文章还介绍了几种常见的优化技术,如缓存节点指针和批量处理,以进一步提升遍历性能。 ... [详细]
  • 在洛谷 P1344 的坏牛奶追踪问题中,第一问要求计算最小割,而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值,可以在求解最小割时优先选择边数较少的方案,从而同时解决两个问题。这种策略不仅简化了问题的求解过程,还确保了结果的最优性。 ... [详细]
  • 本文介绍了如何在iOS平台上使用GLSL着色器将YV12格式的视频帧数据转换为RGB格式,并展示了转换后的图像效果。通过详细的技术实现步骤和代码示例,读者可以轻松掌握这一过程,适用于需要进行视频处理的应用开发。 ... [详细]
  • 本文探讨了 Java 中 Pair 类的历史与现状。虽然 Java 标准库中没有内置的 Pair 类,但社区和第三方库提供了多种实现方式,如 Apache Commons 的 Pair 类和 JavaFX 的 javafx.util.Pair 类。这些实现为需要处理成对数据的开发者提供了便利。此外,文章还讨论了为何标准库未包含 Pair 类的原因,以及在现代 Java 开发中使用 Pair 类的最佳实践。 ... [详细]
  • 寒假作业解析:第三周 2月12日 第7题
    尽快完成之前的练习任务!每日一练2.1 Problem A Laurenty and Shop 的题目要求是选择两条不同的路线以最小化总的等待时间。简要分析:通过对比不同路线的等待时间,可以找到最优解。此问题可以通过动态规划或贪心算法来解决,具体取决于路线的复杂性和约束条件。 ... [详细]
  • 第六章:枚举类型与switch结构的应用分析
    第六章深入探讨了枚举类型与 `switch` 结构在编程中的应用。枚举类型(`enum`)是一种将一组相关常量组织在一起的数据类型,广泛存在于多种编程语言中。例如,在 Cocoa 框架中,处理文本对齐时常用 `NSTextAlignment` 枚举来表示不同的对齐方式。通过结合 `switch` 结构,可以更清晰、高效地实现基于枚举值的逻辑分支,提高代码的可读性和维护性。 ... [详细]
  • 2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南
    2012年9月12日,优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分,有一道题目涉及中国人的血型分布情况,具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中,至少有一人为B型血的概率不低于90%,则需要选取的最少人数是多少?该问题不仅考察了概率统计的基本知识,还要求考生具备一定的逻辑推理能力。 ... [详细]
  • 蓝桥杯物联网基础教程:通过GPIO输入控制LED5的点亮与熄灭
    本教程详细介绍了如何利用STM32的GPIO接口通过输入信号控制LED5的点亮与熄灭。内容涵盖GPIO的基本配置、按键检测及LED驱动方法,适合具有STM32基础的读者学习和实践。 ... [详细]
  • 本指南从零开始介绍Scala编程语言的基础知识,重点讲解了Scala解释器REPL(读取-求值-打印-循环)的使用方法。REPL是Scala开发中的重要工具,能够帮助初学者快速理解和实践Scala的基本语法和特性。通过详细的示例和练习,读者将能够熟练掌握Scala的基础概念和编程技巧。 ... [详细]
  • Objective-C 中的委托模式详解与应用 ... [详细]
  • 如何精通编程语言:全面指南与实用技巧
    如何精通编程语言:全面指南与实用技巧 ... [详细]
  • Vue ElementUI 实现邮箱地址自动补全功能详解 ... [详细]
  • 手指触控|Android电容屏幕驱动调试指南
    手指触控|Android电容屏幕驱动调试指南 ... [详细]
  • 本文探讨了 Kafka 集群的高效部署与优化策略。首先介绍了 Kafka 的下载与安装步骤,包括从官方网站获取最新版本的压缩包并进行解压。随后详细讨论了集群配置的最佳实践,涵盖节点选择、网络优化和性能调优等方面,旨在提升系统的稳定性和处理能力。此外,还提供了常见的故障排查方法和监控方案,帮助运维人员更好地管理和维护 Kafka 集群。 ... [详细]
  • 本文总结了JavaScript的核心知识点和实用技巧,涵盖了变量声明、DOM操作、事件处理等重要方面。例如,通过`event.srcElement`获取触发事件的元素,并使用`alert`显示其HTML结构;利用`innerText`和`innerHTML`属性分别设置和获取文本内容及HTML内容。此外,还介绍了如何在表单中动态生成和操作``元素,以便更好地处理用户输入。这些技巧对于提升前端开发效率和代码质量具有重要意义。 ... [详细]
author-avatar
desn
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有