锐客网

  1. 首页 > it技术 > >

洛谷|过河(dp+路径压缩)

【洛谷|过河(dp+路径压缩)】洛谷|过河(dp+路径压缩)
文章图片

dp+路径压缩

#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int N=1e6+10; int n,m,t,s,l,ans=N; int a[N],d[N],vis[N]; //路径压缩 int dp[N]; //储存最小石子数 /* void dfs(int x,int cnt) { if(x>=l) { ans=min(cnt,ans); return ; } if(cnt>=ans) return; for(int i=s; i<=t; i++) { if(vis[x+i]) { dfs(x+i,cnt+1); } else dfs(x+i,cnt); } } */ //dfs超时好多...分类明明是搜索... int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>l; cin>>s>>t>>m; for(int i=1; i<=m; i++) { cin>>a[i]; } sort(a+1,a+m+1); for (int i=1; i<=m; i++) d[i]=(a[i]-a[i-1])%2520; //要对1~10的最小公倍数取余，压缩路径的核心 for (int i=1; i<=m; i++) { a[i]=a[i-1]+d[i]; vis[a[i]]=1; //此处有石子，标记 } l=a[m]; //压缩路径后的总长度 //dfs(0,0); for(int i=0; i<=l+t; i++) dp[i]=m; dp[0]=0; for(int i=1; i<=l+t; i++) { for(int j=s; j<=t; j++) { if(i>=j) dp[i]=min(dp[i],dp[i-j]); dp[i]+=vis[i]; } } for(int i=l; i<=l+t; i++) ans=min(ans,dp[i]); cout<

    推荐阅读


    上一篇：canvas|根据canvas画一条平滑的渐变线段。

    下一篇：钱云科技第九届“军魂打造”特训营（敢于承担，心怀感恩）