【双指针优化DP】The 2022 Hangzhou Normal U Summer Trials H

比眉伴天荒 2024-03-22 21:47 61阅读 0赞

[Problem - H - Codeforces][]

题意：

![5f14277b0ebb4d30958baffe65902c3e.png][]

![ffbda165d130469ca6e390f9d5f33bc9.png][]

思路：

首先很明显是DP

因为只有1e6个站点，因此可以以站点作为阶段

注意到K很小，因此可以尝试把这个当作第二维  
设dp\[i\]\[j\]为到达第i个站点，已经花了j元钱的最小步数

然后就想了一个n^2的做法，枚举两个指针，第i个站点从第p个站点转移，讨论是走过来的还是骑过来的，计算贡献

但是这样n^2肯定超时，因此我们去考虑特殊性质来枚举上一个状态

特殊性质是，K很小，因此考虑去枚举这次花了l元钱到第i个站点

但是这样的话从什么位置转移过来就不知道了，因此需要预处理从位置和花的钱数的关系

![2f409ebe71974fa6b5ce68397810e243.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxv=1e6+10;
    const int mod=1e9+7;
    
    int N,P,S,K;
    int a[mxn],dp[mxn][6],lx[6];
    
    void solve(){
    	cin>>N>>P>>S;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	cin>>K;
    	memset(dp,0x3f,sizeof(dp));
    	for(int i=0;i<=K;i++) dp[1][i]=a[1],lx[i]=1,dp[0][i]=0;
    	for(int i=1;i<=N;i++){
    		for(int j=0;j<=K;j++){
    			while(a[i]-a[lx[j]]>j*S) lx[j]++;
    			dp[i][j]=dp[i-1][j]+a[i]-a[i-1];
    			for(int l=1;l<=j;l++){
    				dp[i][j]=min(dp[i][j],dp[lx[l]][j-l]);
    			} 
    		}
    	}
    	int ans=1e9;
    	for(int i=1;i<=N;i++) ans=min(ans,dp[i][K]+P-a[i]);
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - H - Codeforces]: https://codeforces.com/gym/103736/problem/H
[5f14277b0ebb4d30958baffe65902c3e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8383a621fa0a41c5b427d50329ddebc5.png
[ffbda165d130469ca6e390f9d5f33bc9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/0ac518f6275848e2a94af6b0e9963377.png
[2f409ebe71974fa6b5ce68397810e243.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/85c0ddc4d6564533bac8e1f89fea2197.png