解题思路:
注意事项:
参考代码:
#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语言训练-求函数值 (C语言代码)浏览:931 |
C语言程序设计教程(第三版)课后习题9.2 (Java代码)浏览:611 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:636 |
printf基础练习2 (C语言代码)浏览:942 |
Pascal三角 (C语言代码)格式错误浏览:519 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:798 |
用筛法求之N内的素数。 (C++代码)浏览:692 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:1913 |
1050题解(结构体数组与结构体指针的使用)浏览:1107 |
简单的事情 (C语言代码)浏览:633 |