解题思路:
注意事项:
参考代码:
#include<iostream> #include<algorithm> #include<algorithm> #include<stdio.h> #include<cstdio> #include<cmath> #include<cstdlib> using namespace std;int a[105],d[105],stone[350000];int f[350000]; int main(){ int l,s,t,m; cin>>l>>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]; stone[a[i]]=1; //此处有石子,标记 } l=a[m]; //压缩路径后的总长度 for (int i=0;i<=l+t;i++) f[i]=m; //f[i]表示到位置i最少能踩到的石子数 f[0]=0; //以上是初始化,接下来是动归 for (int i=1;i<=l+t;i++) for (int j=s;j<=t;j++) { if (i-j>=0) f[i]=min(f[i],f[i-j]); //状态转移方程 f[i]+=stone[i]; } int ans=m; for (int i=l;i<l+t;i++) ans=min(ans,f[i]); cout<<ans<<endl; return 0; }
0.0分
2 人评分
化学品问题 (C语言代码)浏览:1329 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:772 |
C语言程序设计教程(第三版)课后习题3.7 (C++代码)浏览:988 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1066 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:509 |
C语言训练-数字母 (C语言代码)浏览:649 |
简单的for循环浏览:1408 |
本人酷爱递归实现很多问题,这里也是浏览:547 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:2090 |
用筛法求之N内的素数。 (C语言代码)浏览:664 |