过河(状态压缩，dp)

描述

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

对于30%的数据，L <= 10000；
对于全部的数据，L <= 10^9。

格式

输入格式

输入的第一行有一个正整数L（1 <= L <= 10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

输出格式

输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。

样例1

样例输入1[复制]

样例输出1[复制]

限制

来源

NOIp2005 第二题

dp都能看出来，但是数据范围太大，所以无法就这样dp,因为有时两个石头间的间距会很大，这样里面就可以压缩。

首先他给你步数[p，q]，如果当你踩在一个点上时，你用p，p+1,步去走，当某个点距离这个点>=p(p-1)时就都可以由这个点到达。

证明：距p*(p-1),可以由这个点走(p-1)个p

p*(p-1)+1=(p-2)*(p)+p+1;

p*(p-1)+2=(p-3)*p+2*(p+1);

p*(p-1)+p-1=(p-1)*(p+1),

p*p=p*p

然后按上面在次可达所有的点(>=p*(p-1));

那么好了，由于两个点间隔大a[i]-a[i-1]-2*q>p*(p-1)的时候，为啥取这距离是因为，在前一个有石头的地方，假设前面的最小值已经确定好，按最大步数可以确定这个石头及石头以后（a[i-1]+p）处，这边是用dp解决，不用压缩，因为前面计算好了，那么下一个石头点前p个点加上石头点本身可以dp缺点这个石头及石头以后（a[i]+p），所以关键是要确定a[i-p]---a[i]的最小值，所以当之间的a[i]-a[i-1]-2*q>p*(p-1)时，因为在a[i-1]--a[i]间是没有石头的，所以根据上面的结论，a[i-p]---a[i]的最小值每个值都可以由a[i-1]---（a[i-1]+p）来得到，且为这些个数的最小值，那么问题就解决啦。当两个点a[i]-a[i-1]-2*q《=p*(p-1)，因为之间的距离小，所以直接dp就行。还有就是p=q时另外讨论就行。

 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<string.h>

 5 #include<stdlib.h>

 6 #include<queue>

 7 #include<map>

 8 using namespace std;

 9 int a[200];

10 int qiao[30000];

11 int flag[30000];

12 int N=500;

13 int main(void)

14 {

15     int n,i,j,k,p,q;

16     scanf("%d",&k);

17     scanf("%d %d %d",&p,&q,&n);

18     for(i=1; i<=n; i++)

19         scanf("%d",&a[i]);

20     a[i]=k;

21     if(p==q)

22     {

23         int ans=0;

24         for(i=1; i<=n; i++)

25         {

26             if(a[i]%p==0)

27             {

28                 ans++;

29             }

30         }

31         printf("%d\n",ans);

32     }

33     else

34     {

35         sort(a+1,a+n+1);

36         int rr;

37         memset(flag,0,sizeof(flag));

38         fill(qiao,qiao+30000,N);

39         for(i=1; i<=n+1; i++)

40         {

41             if(i!=1)flag[a[i-1]]=2;

42             if(a[i]-a[i-1]-2*q>p*(p-1))

43             {

44                 for(j=(a[i-1]+q+1); j<=(a[i-1]+2*q+2); j++)

45                 {

46                     flag[j]=1;

47                 }

48                 int s=a[i]-(j-1);

49                 for(j=i; j<=n+1; j++)

50                 {

51                     a[j]-=s;

52                 }

53             }

54         }

55         rr=a[n+1];

56         qiao[0]=0;

57         int uu=0;

58         for(i=0; i<=rr; i++)

59         {

60             if(flag[i]==0||(flag[i]==2&&flag[i-1]==0||flag[i-1]==2))

61             {

62                 for(j=p; j<=q; j++)

63                 {

64                     if(i-j<0)

65                     {

66                         break;

67                     }

68                     else

69                     {

70                         int ss=0;

71                         if(flag[i]==2)

72                             ss=1;

73                         qiao[i]=min(qiao[i],qiao[i-j]+ss);

74                     }

75                 }

76             }

77             else if(flag[i])

78             {

79                 int ss=0;

80                 if(flag[i]==2)

81                     ss=1;

82                 for(j=0; j<=q; j++)

83                 {

84                     qiao[i]=min(qiao[i],qiao[a[uu]+j]+ss);

85                 }

86             }

87             if(flag[i]==2)uu++;

88         }

89         printf("%d\n",qiao[rr]);

90     }

91     return 0;

92 }

巴特西

过河(状态压缩，dp)

描述

格式

输入格式

输出格式

样例1

样例输入1[复制]

样例输出1[复制]

限制

来源

最新文章

热门文章