【简单DP】P3842 [TJOI2007]线段

傷城~ 2024-03-16 16:23 97阅读 0赞

[P3842 \[TJOI2007\]线段 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P3842 _TJOI2007_ - _ _ _ _luogu.com.cn]

题意：

![28aecac9e4224f76a810bc10871be349.png][]

思路：

考虑线性DP

把行作为阶段去DP

然后观察样例可知有一个很显然的结论：为了保证路径最小，要不是从左端点下去的，要不是从右端点下去的

![756bb20b9522461682cc84e31ee51f6e.png][]

那么可以这样设计状态：

设dp\[i\]\[0\]为第i行，从左端点下去的最短路径

dp\[i\]\[1\]为第i行，从右端点下去的最短路径

然后就能转移了

当前从左端点下去的，上一行可能从左/右端点下来，讨论一下即可

注意第一行要初始化

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e4+10;
    
    int N;
    int L[mxn],R[mxn];
    int dp[mxn][2];
    
    void solve(){
        cin>>N;
        for(int i=1;i<=N;i++) cin>>L[i]>>R[i];
        dp[1][0]=R[1]-1+1+R[1]-L[1];
        dp[1][1]=R[1]-1+1;
        for(int i=2;i<=N;i++){
            dp[i][0]=min(dp[i-1][0]+abs(R[i]-L[i-1])+1+R[i]-L[i],dp[i-1][1]+abs(R[i-1]-R[i])+1+R[i]-L[i]);
            dp[i][1]=min(dp[i-1][0]+abs(L[i-1]-L[i])+1+R[i]-L[i],dp[i-1][1]+abs(R[i-1]-L[i])+1+R[i]-L[i]);
        }
        cout<<dp[N][1]+N-(R[N]+1)<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[P3842 _TJOI2007_ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P3842
[28aecac9e4224f76a810bc10871be349.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/8a7879269f0c40b4a2d082a07f1beb76.png
[756bb20b9522461682cc84e31ee51f6e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/212247eff6a44680b457875cbc18cf69.png