题目来源：洛谷P1052
思路
一开始觉得是贪心
但是仔细一想不对 是DP
再仔细一看数据不对 有点大
如果直接存下的话 显然会炸
那么就需要考虑离散化
因为一步最大跳10格 那么我们考虑从1到10都跳一遍
所以最大公倍数为2520
那么我们就可以枚举两个石头中间的长度mod 2520 即可缩短总长度
详细见代码
代码
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 350000
#define mod 2520
int l,s,t,m,ans;
int f[maxn],stone[maxn],a[
110],d[
110];
int main()
{
cin>>l>>s>>t>>
m;
for(
int i=
1;i<=m;i++) cin>>
a[i];
sort(1+a,
1+a+m);
//可能是乱序
for(
int i=
1;i<=m;i++) d[i]=(a[i]-a[i-
1])%mod;
//枚举两个石头之间的长度
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[
0]=
0;
//起点为0
for(
int i=
1;i<=l+t;i++)
//l+t是因为可能会跳出去
{
for(
int j=s;j<=t;j++)
//枚举步数
{
if(i-j>=
0)
//边界条件
f[i]=min(f[i],f[i-j]);
//取最小
f[i]+=stone[i];
//如果有石头就会加1
}
}
ans=m;
//初始化
for(
int i=l;i<l+t;i++)
//枚举终点到终点后最大步数的所有答案最小值
ans=
min(ans,f[i]);
cout<<
ans;
}
转载于:https://www.cnblogs.com/BrokenString/p/9876379.html
