过河
过河
https://ac.nowcoder.com/acm/problem/16655
离散化+dp
观察数据范围,桥的距离很长,但是石子很少,所以中间会存在相隔很远的石子,所以我们要对他们的中间的路径进行压缩,也就是离散化
#include<bits/stdc++.h> using namespace std; typedef long long ll; int l; int s,t,m; int dp[20005]; int vis[20005]; //是否有石子 int main() { scanf("%d",&l); scanf("%d%d%d",&s,&t,&m); vector<int> v(m); for(auto &i:v) scanf("%d",&i); v.push_back(0); v.push_back(l); sort(v.begin(),v.end()); vector<int> vv(v); for(int i=1;i<(int)vv.size();i++) { //离散化 if(vv[i]-vv[i-1]>100) v[i]=v[i-1]+100+(vv[i]-vv[i-1]-100)%t; else v[i]=v[i-1]+vv[i]-vv[i-1]; } for(int i=1;i<(int)v.size()-1;i++) vis[v[i]]=1; memset(dp,0x3f,sizeof dp); dp[0]=vis[0]; for(int i=s;i<=v.back()+100;i++) { for(int j=s;j<=t;j++) { if(j<=i) dp[i]=min(dp[i],dp[i-j]+vis[i]); } } printf("%d\n",*min_element(dp+v.back(),dp+v.back()+100)); return 0; }