讨论 / 有没有c++源码啊,发一下,帮帮忙
wnzxpsz 2015-04-12 15:41:25
点我顶贴 收藏 删除
有没有c++源码啊,发一下,帮帮忙
#1 tjb1998@2015-08-08 21:19:06
回复 删除
#include<iostream>

#include<algorithm>

using namespace std;

#define INF 10000001

int l,s,t,m;

int a[101];

int w[10101];

int f[10101];

int main()

{

cin>>l;

cin>>s>>t>>m;

for(int i=1;i<=m;i++)

cin>>a[i];

sort(a+1,a+m+1);

if(s==t)

{

int ans=0;

for(int i=1;i<=m;i++)

if(a[i]%s==0)

ans++;

cout<<ans<<endl;

//system("pause");

return 0;

}

a[0]=0;

a[m+1]=l;

for(int i=0;i<=m;i++)

if(a[i+1]-a[i]>90)

a[i+1]=a[i]+(a[i+1]-a[i])%90;

int p=a[m+1];

for(int i=1;i<=m;i++)

w[a[i]]=1;

for(int i=0;i<=p;i++)f[i]=INF;

f[0]=0;

for(int i=s;i<=p;i++)

for(int j=s;j<=t;j++)

if(i-j>=0)

f[i]=min(f[i],f[i-j]+w[i]);

cout<<f[p]<<endl;

/*for(int i=0;i<=p;i++)

cout<<f[i]<<" ";*/

//system("pause");

return 0;

}

#2 hnrw_6@2017-04-07 21:01:19
回复 删除
回复 #1 tjb1998:那个90是怎么来的??
#3 404@2017-07-24 11:32:59
回复 删除
回复 #2 hnrw_6:不知道为什么,换成80也能过。
#4 Magna_Medivh@2017-07-31 22:03:27
回复 删除
回复 #2 hnrw_6:90 = 9 * 10。我觉得是这样的:总长度L很长,但是石头数(关心点)很少,考虑离散化。但是离散化标准若是石头所在点是不行的,因为跳跃是连贯过程。但是L显然是冗余的,所以考虑“缩路”:我不关心相邻两石头间是怎么跳的,只关心要到下一块石头时青蛙与下一块石头间的可能距离。然而,若两石头间距离很长,则要到下一块石头时青蛙与下一块石头间的可能距离可以是s到t的任意值(显然),故距离再长就没意义了,而这个上界(粗略)便是9*10
查看更多回复
提交回复