青蛙过河解题报告"/>
青蛙过河解题报告
题目链接:.php?id=1003
虽然是高中做过的题,但当时并不是特别理解(尽管A掉了,还是在看来题解的情况下)。
现在再次做这道题,与之前不同的是,知道要用状态压缩,可是怎么压,还是不清楚。于是先考虑去掉大于10+t 的没有石子的位置(设每一次去掉的位置的数量为tmp),后面所有的石子和桥尾的位置都减去tmp(当时觉得这是个不错的想法),提交后却是运行错误(数组越界、非法调用、系统堆栈溢出)。后来看题解说压缩大于t*(t-1) 的部分,还是运行错误。后来宝宝学长给我了最大的一组数据,单步运行后发现,压缩状态的时候忘记把L与最后一个石子之间的距离压缩了,郁闷死了。。。。。
状态转移方程:f[i]=min{f[i-k]};if (fx[i]) f[i]++; f[i]表示从0到i踩到的最少石子数,fx[i]表示i位置上有无石子。
#define min(a,b) (a)<(b)?(a):(b)
#include<stdio.h>
int a[110];
int f[2000000];
bool fx[2000000];
int main()
{
int l,s,t,m,i,j,tmp,pos;
scanf("%d",&l);
scanf("%d%d%d",&s,&t,&m);
for (i=0;i<m;i++)
{
scanf("%d",&a[i]);
}
a[m]=l; pos=m;
m++;
if (s==t) //特殊情况
{
tmp=0;
for (i=0;i<m;i++)
if (a[i]%s==0) tmp++;
printf("%d",tmp);
return 0;
}
for (i=m-1;i>=0;i--) //排序,准备压缩
for (j=0;j<i;j++)
if (a[j]>a[j+1])
{
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
if (j+1==pos) pos--;
}
if (a[0]>t*s) //开始压缩
{
tmp=a[0]-t*s;
for (j=0;j<m;j++) a[j]-=tmp;
}
for (i=1;i<m;i++)
if (a[i]-a[i-1]>t*(t-1))
{
tmp=(a[i]-a[i-1]-t*(t-1));
for (j=i;j<m;j++) a[j]-=tmp;
}
for (i=0;i<m;i++) fx[a[i]]=true; //准备dp与dp
for (i=s;i<=t;i++)
if (fx[i]) f[i]++;
for (i=t+1;i<=a[pos]+t-1;i++)
{
f[i]=(1<<31)-1;
for (j=s;j<=t;j++)if (i-j>=s) f[i]=min(f[i],f[i-j]);
if (fx[i]) f[i]++;
}
tmp=(1<<31)-1;
for (i=a[pos];i<=a[pos]+t-1;i++) tmp=min(tmp,f[i]);
printf("%d",tmp);
return 0;
}
更多推荐
青蛙过河解题报告
发布评论