讨论 / 不要怕我来告诉你们ac代码,我是救世主
zxj200408 2017-08-15 15:31:32
点我顶贴 收藏 删除
#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#define MAXN 100020

#define INF 100000000

using namespace std;

int min(int a,int b)

{

if(a<b)

return a;

return b;

}

int main()

{

int stone[200]; //stone[i]表示第i个石子距起点的长度

int pos[MAXN]={0};//pos[i]=1表示距起点距离为i的点有一个石子

int f[MAXN]={0}; //f[i]=到距起点距离为i的点要经过的最少石子数

int distance=0,L,S,T,M,oldlen,ziplen,i,j; //distance=压缩后每个石子的距离,oldlen=压缩前的石子距离,ziplen=压缩后的石子距离

scanf("%d%d%d%d",&L,&S,&T,&M);

for(i=1;i<=M;i++)

scanf("%d",&stone[i]);

sort(stone+1,stone+M+1); //将石子距起点长度升序排序

for(i=1;i<=M;i++) //循环,压缩石子间的距离

{

oldlen=stone[i]-stone[i-1]; //压缩前的石子间距

ziplen=T; //压缩后的石子间距=青蛙单次跳跃最大距离

if(ziplen>oldlen) ziplen=oldlen; //如果压缩距离大于原始距离,压缩距离等于原始距离

distance+=ziplen; //更新压缩后最后一个石子的位置

pos[distance]=1; //新的最后一个石子的位置标记为1,有石子

}

// f[0]=1;

for(i=1;i<=distance+T;i++)

//由于青蛙最后一次跳跃的落点位置可能大于压缩后总距离distance,但它一定小于distance+T

//因此循环终点定为distance+T,i=当前青蛙的位置

{

int minn=INF; //到达i点经过的最少石子数

for(j=i-T;j<=i-S;j++) //要想到达i,j最近要到i-T,最远到i-S

{

if(j>=0)

minn=min(minn,f[j]); //更新到达i点要经过的最少石子数(i点的石子不算)

}

f[i]=minn+pos[i];

}

int ans=INF;

for(i=distance;i<=distance+T;i++) //最终落点在区间[distance,distance+T],寻找最优解的落点

ans=min(ans,f[i]);

if(S==T) //如果最小跳跃距离等于最大跳跃距离,那么ans=距离是S(T)的倍数的石子数

{

ans=0;

for(i=1;i<=M;i++)

{

if(stone[i]%S==0) //第i个石头的距离是S的倍数

ans++;

}

}

printf("%d\n",ans);

return 0;

}

查看更多回复
提交回复