首页 > 代码库 > [题解]RQNOJ PID87 过河
[题解]RQNOJ PID87 过河
链接：http://www.rqnoj.cn/problem/87
思路：动态规划
定义f[i][j]表示到达第 i 块给定石头用了 j 块添加石头的最少步数。
转移方程：f[i][j]=min{f[k][j-tmp[pos[i]-pos[k]]+1]+tmp[pos[i]-pos[k]]} ，其中0<=k<i 且tmp[pos[i]-pos[k]]-1<=j
其中pos[i]表示第 i 块给定石头的坐标，tmp[i]表示跨过距离 i 需要添加的石头（相当于从坐标0出发到坐标 i ，注意坐标 i 处没有石头，需要放1块）。tmp[i]可以预处理出来，tmp[0]=0，tmp[i]=min{tmp[i-j]}+1，其中S<=j<=T且j<= i 。
最后统计答案，枚举最后落脚的给定石头 i 、用掉的石头 j 以及最后落脚的添加石头的位置 k （L-T+1<=k<=L且k>=pos[i]且j+tmp[k-pos[i]]<=M），ans=min{f[i][j]+tmp[k-pos[i]]+1} 。如果ans=INF即无法到达对岸，需要计算出能走的最远距离，那么枚举最后落脚的给定石头 i ，如果f[i][j]<INF，ans=max{pos[i]+(M-j)*T} 。
我的实现：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 #define MaxL 100020 6 #define MaxN 120 7 #define MaxM 20020 8 #define INF 100020 9 int tmp[MaxL],pos[MaxN],f[MaxN][MaxM];10 int L,N,M,S,T;11 int ans;12 inline void Get_int(int &Ret)13 {14 char ch;15 bool flag=false;16 for(;ch=getchar(),ch<‘0‘||ch>‘9‘;)17 if(ch==‘-‘)18 flag=true;19 for(Ret=ch-‘0‘;ch=getchar(),ch>=‘0‘&&ch<=‘9‘;Ret=Ret*10+ch-‘0‘);20 flag&&(Ret=-Ret);21 }22 int main()23 {24 Get_int(L);Get_int(N);Get_int(M);Get_int(S);Get_int(T);25 int i,j,k;26 for(i=1;i<=N;++i)27 Get_int(pos[i]);28 memset(tmp,0x3f,sizeof(tmp));//预处理 tmp[i]表示距离i放的最少石头数29 tmp[0]=0;30 for(i=1;i<=L;++i)31 for(j=S;j<=T&&i>=j;++j)32 tmp[i]=min(tmp[i],tmp[i-j]+1);33 memset(f,0x3f,sizeof(f));//边界34 f[0][0]=0;35 for(i=1;i<=N;++i)//dp f[i][j]表示到第i块给定石头用了j块添加石头的最少步数36 for(j=0;j<=M;++j)37 for(k=0;k<i;++k)38 if(tmp[pos[i]-pos[k]]-1<=j)39 f[i][j]=min(f[i][j],f[k][j-tmp[pos[i]-pos[k]]+1]+tmp[pos[i]-pos[k]]);40 ans=INF;41 for(i=0;i<=N;++i)//统计答案42 for(j=0;j<=M;++j)43 for(k=L;k>=L-T+1&&k>=pos[i];--k)44 if(j+tmp[k-pos[i]]<=M)45 ans=min(ans,f[i][j]+tmp[k-pos[i]]+1);46 if(ans==INF)//计算最远到达的坐标47 {48 ans=0;49 for(i=0;i<=N;++i)50 for(j=0;j<=M;++j)51 if(f[i][j]<INF)52 ans=max(ans,pos[i]+(M-j)*T);53 }54 printf("%d\n",ans);55 return 0;56 }
效率：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。