dp路径poj1661

C/C++/C# 更新时间：2026-04-01 23:10:40 发布时间：1633天前 IT归档最新发布模块sitemap 名妆网法律咨询聚返吧英语巴士网伯小乐网商动力

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include //io控制头文件 cout<M){
        dp[0][i]=inf;
     }
     else dp[0][i]=e[i].h;
}
void righttime(int i){
     int k=i+1;
     while(k<=n&&e[i].h-e[k].h<=M){
        if(e[k].lx<=e[i].rx&&e[i].rx<=e[k].rx){
            dp[1][i]=e[i].h-e[k].h+min(dp[0][k]+e[i].rx-e[k].lx,dp[1][k]+e[k].rx-e[i].rx);
            return ;
        }
        k++;
     }
     if(e[i].h-e[k].h>M){
        dp[1][i]=inf;
     }
     else dp[1][i]=e[i].h;
}
int main()
{
    cin>>t;
    while(t--){
        ms(dp,inf);
        e[0].lx=-20000,e[0].rx=20000,e[0].h=0;
        cin>>n>>x>>y>>M;
        e[1].lx=x,e[1].rx=x,e[1].h=y;
        for(int i=2;i<=n+1;i++){
            scanf("%d%d%d",&e[i].lx,&e[i].rx,&e[i].h);
        }
        sort(e,e+2+n);
        for(int i=n;i>=0;i--){
            lefttime(i);
            righttime(i);
        }
        cout< 
1661 -- Help Jimmy 
只考虑最近路径的由下往上搜索，巧妙利用return

转载请注明：文章转载自 www.mshxw.com

本文地址：https://www.mshxw.com/it/311527.html

上一篇 c++实现下三角矩阵的取值和存值

下一篇 docker-rabbitmq+redis+haproxy

C/C++/C#相关栏目本月热门文章

关于我们文章归档网站地图联系我们