[题解]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 }

效率：

巴特西

[题解]RQNOJ PID87 过河

最新文章

热门文章