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

Problem - H - Codeforces

题意：

 

思路：

首先很明显是DP

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

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

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

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

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

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

Code：

#include <bits/stdc++.h>#define int long longusing 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;
}