如果兩個點之間的距離大于t^2，就另他們之間的距離為t^2。如果s!=t，且距離大于t^2，一定存在一種走法，可以從前一個點走到下一個點。
以下是我的代碼：
#include<stdio.h>
#include<string.h>
#define maxm 107
#define maxl 15007
#define INF 2000007
#define min(a,b) (a<b?a:b)
long l,s,t,m,pos[maxm],d[maxl];
bool a[maxl];
void swap(long &a,long &b)
{
long t=a;a=b;b=t;
}
void Qsort(long *a,long begin,long end)
{
long i=begin,j=end,mid=a[(begin+end)/2];
do{
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j)
{
swap(a[i],a[j]);
i++;j--;
}
}while(i<=j);
if(begin<j) Qsort(a,begin,j);
if(i<end) Qsort(a,i,end);
}
int main()
{
/*
freopen("river.in","r",stdin);
freopen("river.out","w",stdout);
//*/
scanf("%ld%ld%ld%ld",&l,&s,&t,&m);
pos[0]=0;
for(long i=1;i<=m;i++)
scanf("%ld",&pos[i]);
if(s==t)
{
long ans=0;
for(long i=1;i<=m;i++)
if(pos[i]%s==0)
ans++;
printf("%ld\n",ans);
return 0;
}
Qsort(pos,0,m);
memset(a,false,sizeof(a));
for(long i=1;i<=m;i++)
{
if(pos[i]-pos[i-1]>=t*t)
{
long tmp=pos[i]-(pos[i-1]+t*t);
pos[i]=pos[i-1]+t*t;
for(long j=i+1;j<=m;j++)
pos[j]-=tmp;
}
a[pos[i]]=true;
}
l=pos[m]+t*t;
for(long i=1;i<=l;i++) d[i]=INF;
d[0]=0;
for(long i=s;i<=l;i++)
for(long j=s;j<=t;j++)
d[i]=min(d[i],d[i-j]+a[i]);
printf("%ld\n",d[l]);
return 0;
}
posted on 2010-03-08 19:40
lee1r 閱讀(285)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃