题目链接传送门

E. Not Escaping

题目大意是有n * m个房间，然后有k个梯子，在每一层的房间中行动时会减少生命值减少,在第 $i$ 层从 $(i, j)$ 移动到 $(i, k)$ 会减少 $x_{i} * ∣ k - j ∣$ 的声明，从梯子移动会增加h生命，梯子只有向上的，那么求出从 $(1, 1)$ 到 $(n, m)$ 的减少最小的声明值。

数据范围 $n,m,k \le 1e5$

spfa解法

那么先进行普通的考虑，可以将每个点之间进行连边，由于只有梯子能够上下，那么只有梯子有用，那么只有梯子的上下两个房间和出入口有用，那么将这些关键房间离散化，连边，建图，可以使用spfa找到最长路，那么最长路就是题目要求的答案，这里点数最多 $2 e 5$ 边数(梯子的边，同一层之间的边)最多 $2 e 5 + 1 e 5$ ，那么由于spfa的期望时间复杂度是 $O (p m)$ ,但是最坏时间复杂度是 $O (n * m)$ ，所以大概率不是正解，但是常数小可以卡着cf的极限在选c++14，1964ms通过，选c++20可以到1200ms。

代码

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
typedef long long ll ;
typedef pair<int,int> pii ;
const int N = 1e6 + 100 , M = 2 * N ;
const ll INF = 0x3f3f3f3f3f3f3f3f ;
 
int n,m,k ;
int h[N],e[M],ne[M],idx ;  // 链式前向星建图
int x[N] ;  // 每层的x
ll dist[N],w[M],q[N] ;  //spfa用到的dist数组，w是建图数组，q是spfa的模拟循环队列
bool st[N] ;// spfa判重数组
vector<pii> nums ;  // 离散化点数组
struct node
{
    pii s,t ;
    int h ;
}lad[N] ;  // 存储梯子信息
 
 
char *p1,*p2,buf[100000];  // 快读模板
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read()
{
    int x=0,f=1;
    char ch=nc();
    while(ch<48||ch>57)
    {
        if(ch=='-')
            f=-1;
        ch=nc();
    }
    while(ch>=48&&ch<=57)
        x=x*10+ch-48,ch=nc();
   	return x*f;
}
 
 
void init(){  // 多组测试样例 初始化数组信息
    nums.clear() ;
    idx = 0 ;
    nums.push_back({1,1}) ;
    nums.push_back({n,m}) ;
    for(int i = 0 ; i <= k * 2  + 2; i ++ ) h[i] = - 1;
}
 
int get(pii t){  // 获得离散化后的点
    return lower_bound(nums.begin(),nums.end(),t) - nums.begin() ;
}
 
void add(int a,int b,ll c){  // 链式前向星建边
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++ ; 
}
 
void spfa(){  // spfa跑最长路
    for(int i = 0 ; i <= nums.size() ; i ++) dist[i] = -INF ;
    int hh = 0 ,tt = 1 ;
    q[0] = get({1,1}),dist[get({1,1})] = 0 ;
 
    while(hh != tt){
        int t = q[hh++] ;
        if(hh == N) hh = 0 ;
 
        st[t] = 0 ;
 
        //cout << "------>" << nums[t].first << " " << nums[t].second << "\n" ;
 
        for(int i = h[t] ; ~ i ; i = ne[i]){
            int j = e[i] ;
 
            if(dist[j] < dist[t] + w[i]){
                //cout << "------>" << nums[j].first << " " << nums[j].second << "\n" ;
                dist[j] = dist[t] + w[i] ;
 
                if(!st[j]){
                    q[tt++] = j  ;
                    if(tt == N) tt = 0 ;
                    st[j] = 1 ;
                }
            }
        }
    }
 
    if(dist[get({n,m})] == -INF) puts("NO ESCAPE") ;  // 如果最后值等于-INF代表无法到达
    else printf("%lld\n",-dist[get({n,m})]) ; // 输出答案
}
 
signed main(){
    int t ;
    t = read() ;
    while(t--){
        n = read() ;
        m = read() ;
        k = read() ;
 
        init() ;
        
        for(int i = 1 ; i <= n ; i++) x[i] = read() ;
 
        for(int i = 0 ; i < k ; i ++){  //存梯子信息
            int a,b,c,d,h ; 
            a = read() ;
            b = read() ;
            c = read() ;
            d = read() ;
            h = read() ;
            lad[i] = {{a,b},{c,d},h} ;
            nums.push_back({a,b}) ;
            nums.push_back({c,d}) ;   
        }
 
        sort(nums.begin(),nums.end()) ;
        nums.erase(unique(nums.begin(),nums.end()),nums.end()) ;
 
        for(int i = 0 ; i < k ;i ++) add(get(lad[i].s),get(lad[i].t),lad[i].h) ;  // 加边梯子
        
        for(int i = 0 ; i + 1 < nums.size() ; i ++){
            if(nums[i].first == nums[i+1].first){  // 这里由于nums离散化数组已经按照x排好序了，所以使用这个来给同一行加边，每一行只需要加相邻两个点的边即可
                ll t = (ll)x[nums[i].first] * (nums[i+1].second - nums[i].second) ;
                add(i,i+1,-t) ;
                add(i+1,i,-t) ;
            }
        }
        
        spfa() ;
    }
    return 0;
}

dp正解

那么经过上面的分析可以知道，可以通过关键的房间来缩少点的数量。那么还有一个性质没有使用，那么就是梯子只能向上，那么有了方向性，其实dp就是一种有固定方向性的图论问题。那么我们可以进行dp，可以知道肯定是每层向上的方向进行dp，每层内部，需要从左向右进行转移，再从右向左进行一次状态转移。那么这个时间复杂度为每个点只会转移3次，所以是 $O (k)$

那么就是正解代码

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

typedef long long ll ;
typedef pair<int,int> pii ;
const int N = 1e6 + 100 , M = 2 * N ;
const ll INF = 0x3f3f3f3f3f3f3f3f ;

int n,m,k ;
ll f[N] ;  // dp数组
ll x[N] ;
vector<int> edge[N] ;  // 记录当前层有那些关键房间
vector<pii> nums ;  // 离散化
struct node
{
    pii s,t ;
    int h ;
};
vector<node> lad[N] ;  // 记录第i层的梯子信息

void init(){  // 初始化信息
    for(int i = 0 ; i <= n ; i++) edge[i].clear(),lad[i].clear() ;

    nums.push_back({1,1}) ;
    nums.push_back({n,m}) ;
    edge[1].push_back(1) ;
    edge[n].push_back(m) ;
}

int get(pii t){  // 离散化获得
    return lower_bound(nums.begin(),nums.end(),t) - nums.begin() ;
}

int main(){
    int t ;
    scanf("%d",&t) ;
    while(t--){
        scanf("%d%d%d",&n,&m,&k) ;

        init() ;

        for(int i = 1 ; i <= n ; i++) scanf("%lld",&x[i]) ;

        for(int i = 0 ; i < k ; i++){
            int a,b,c,d,h ; 
            scanf("%d%d%d%d%d",&a,&b,&c,&d,&h) ;
            lad[a].push_back({{a,b},{c,d},h}) ;
            
            edge[a].push_back(b) ;
            edge[c].push_back(d) ;
            nums.push_back({a,b}) ;
            nums.push_back({c,d}) ;  
        }

        sort(nums.begin(),nums.end()) ;  // 离散化
        nums.erase(unique(nums.begin(),nums.end()),nums.end()) ;

        for(int i = 0 ; i < nums.size() ; i ++) f[i] = -INF ;

        f[get({1,1})] = 0 ;  // 初始化第一个初始点
        for(int i = 1;  i <= n ; i++){
            sort(edge[i].begin(),edge[i].end()) ;  // 判重
            edge[i].erase(unique(edge[i].begin(),edge[i].end()),edge[i].end()) ;
            
            for(int j = 1 ; j < edge[i].size() ;  j++){ // 从左向右dp
                int a = edge[i][j-1],b = edge[i][j] ;
                f[get({i,b})] = max(f[get({i,b})],f[get({i,a})] - x[i] * (b - a)) ;
            }

            for(int j = edge[i].size() - 2 ;j >= 0;j --){ // 从右向左dp
                int a = edge[i][j],b = edge[i][j + 1]  ;
                f[get({i,a})] = max(f[get({i,a})],f[get({i,b})] - x[i] * (b - a)) ;
            }
        
            for(int j = 0 ; j < lad[i].size() ;j++){  // 进行梯子的dp
                f[get(lad[i][j].t)] = max(f[get(lad[i][j].t)],f[get(lad[i][j].s)] + lad[i][j].h) ;
            }
        }

        if(f[get({n,m})] <= -INF / 2) puts("NO ESCAPE") ;  // 这里注意要小于等于-INF/2，，因为可能从梯子转移到终点，会使终点的值稍微增大一点，但是还是不可能到达到
        else printf("%lld\n",-f[get({n,m})]) ;
    }
    return 0;
}

E. Not Escaping (Codeforces Round #766 (Div. 2))

E. Not Escaping

spfa解法

dp正解