沈阳定制网站建设,拓者网室内设计官网app,连接到wordpress,网站网页切换怎么做的Problem - H - Codeforces
题意#xff1a; 思路#xff1a;
首先很明显是DP
因为只有1e6个站点#xff0c;因此可以以站点作为阶段
注意到K很小#xff0c;因此可以尝试把这个当作第二维 设dp[i][j]为到达第i个站点#xff0c;已经花了j元钱的最小步数
然后就想了一…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 mxn1e610;
const int mxv1e610;
const int mod1e97;int N,P,S,K;
int a[mxn],dp[mxn][6],lx[6];void solve(){cinNPS;for(int i1;iN;i) cina[i];cinK;memset(dp,0x3f,sizeof(dp));for(int i0;iK;i) dp[1][i]a[1],lx[i]1,dp[0][i]0;for(int i1;iN;i){for(int j0;jK;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 l1;lj;l){dp[i][j]min(dp[i][j],dp[lx[l]][j-l]);} }}int ans1e9;for(int i1;iN;i) ansmin(ans,dp[i][K]P-a[i]);coutans\n;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __1;//cin__;while(__--)solve();return 0;
}
