P1244 青蛙过河

P1244 青蛙过河
NOI2000
主要思想：
数学归纳法递推压位高精度化归
理解能力和找规律的能力
题意再述：
1.青蛙从上到下必须连续递增或者下面是石墩
而不能是
1 1
2 3
3 4
而且每时每刻都要满足这个条件
2.左岸和右岸都是石堆
公式推导过程：
k=0
h=0 s=1
h=1 s=2 _ _ _
h=2 s=?

当h=1时，共有三个石墩，空石墩有2个，我们可以转移2个青蛙到任意石墩
当h=2时，总石墩数比原来多1，空石墩有3个，我们可以先利用3个空石墩把上面2个小青蛙（1号和2号）移到一个非右岸的一个空石墩上，现在共有2个空石墩，由h=1时
（空石墩有2个，我们可以转移2个青蛙到任意石墩）
，我把下面两个大青蛙，移到右岸，再把，小青蛙移到右岸。完成。

假设当h=x,k=0时，空石墩有x+1个，最多能转移的青蛙数为(1<<x)
当h=x+1时，k=0，空石墩有x+2个，我们可以利用x+1个空石墩把(1<<x)个青蛙移到一个非右岸的一个空石墩上，现在有空石墩h+1个，我们用这x+1个空石墩将下面的(1<<x)个大青蛙移到右岸，现在还是有空石墩x+1个，再用这些把刚才的(1<<x)个小青蛙移到右岸。移动的青蛙总数是h=x时的两倍，故为
（1<<(x+1)）;
所以当k=0时，转移的青蛙数为(1<<h)

要是k>0呢？

我们知道，当k=0时，转移的青蛙数为(1<<h)，单个青蛙可以直接移动，我们把（k+1）只青蛙压成一只青蛙，因为(k+1)只青蛙可以像一只青蛙一样直接移动，why？先把k只青蛙放到k个荷叶上，再把最下面的那只移到目标位置，再把荷叶上的k只青蛙移到最下面的那只上就可以不借助石墩实现(k+1)只青蛙的直接移动。
原来当k=0时，转移的青蛙数为(1<<h)，现在把（k+1）只青蛙压成一只青蛙，所以总数为：
(1<<h)*(k+1)

结束了？？？
完美了？？？

但是这样只是证明了这种解的存在性，并没有证明最优性。有想法的和我继续讨论。

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<ctime>

 #include<cstring>

 #define inf 2147483647

 #define For(i,a,b) for(register long long i=a;i<=b;i++)

 #define p(a) putchar(a)

 #define g() getchar()

 //by war

 //2017.10.19

 using namespace std;

 long long h,k;

 void in(long long &x)

 {

     long long y=;

     char c=g();x=;

     while(c<''||c>'')

     {

     if(c=='-')

     y=-;

     c=g();

     }

     while(c<=''&&c>='')x=x*+c-'',c=g();

     x*=y;

 }

 void o(long long x)

 {

     if(x<)

     {

         p('-');

         x=-x;

     }

     if(x>)o(x/);

     p(x%+'');

 }

 int main()

 {

     in(h),in(k);

     cout<<((<<h)*(k+));

      return ;

 }

巴特西

P1244 青蛙过河

最新文章

热门文章