首页 > ACM题库 > HDU-杭电 > HDU 2842-Chinese Rings-递推-[解题报告]HOJ
2014
02-17

HDU 2842-Chinese Rings-递推-[解题报告]HOJ

Chinese Rings

问题描述 :

Dumbear likes to play the Chinese Rings (Baguenaudier). It’s a game played with nine rings on a bar. The rules of this game are very simple: At first, the nine rings are all on the bar.
The first ring can be taken off or taken on with one step.
If the first k rings are all off and the (k + 1)th ring is on, then the (k + 2)th ring can be taken off or taken on with one step. (0 ≤ k ≤ 7)

Now consider a game with N (N ≤ 1,000,000,000) rings on a bar, Dumbear wants to make all the rings off the bar with least steps. But Dumbear is very dumb, so he wants you to help him.

输入:

Each line of the input file contains a number N indicates the number of the rings on the bar. The last line of the input file contains a number "0".

输出:

Each line of the input file contains a number N indicates the number of the rings on the bar. The last line of the input file contains a number "0".

样例输入:

1
4
0

样例输出:

1
10

题目链接:hdu2842

题意是让求把n个环拆下来需要的最少步数

思路:如果要拆第n个环,那么第n-1个环就必须在竿上,前n-2个环都必须已经被拆下;假设f(n)表示拆第n个环需要的最少步数,那么拆第n个环的时候,第n-1个环在竿上,前n-2个环已经被拆下,那么f(n) = f(n-2)+1,加1是因为拆环的时候需要一步,接下来只剩下第n-1个环了,拆第n-1个环时,第n-2个环必须在竿上,那么就需要在将第n-2个环装在竿上,需要f(n-2)步,再拆第n-1个环,又需要f(n-1)步,则得出递推公式:f(n)
= f(n-2)+1+ f(n-2)+f(n-1),即f(n) = 2*f(n-2)+f(n-1)+1;

接下来就是用矩阵二分幂。。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
#define mod 200907
int n;
struct node
{
    __int64 map[3][3];
}unit,s;
node Mul(node a,node b)
{
    node c;
    int i,j,k;
    for(i = 0; i < 3; i ++)
    for(j = 0; j < 3; j ++)
    {
        c.map[i][j] = 0;
        for(k = 0; k < 3; k ++)
        c.map[i][j] += (a.map[i][k]*b.map[k][j])%mod;
        c.map[i][j] %= mod;
    }
    return c;
}
void Matrix()
{
    while(n)
    {
        if(n&1) unit = Mul(unit,s);
        n >>= 1;
        s = Mul(s,s);
    }
}
int main()
{
    int i,f[3] = {1,1,2};
    while(scanf("%d",&n),n)
    {
        if(n <= 2)
        {
            printf("%d\n",f[n]);
            continue;
        }
        memset(s.map,0,sizeof(s.map));
        s.map[0][0] = 1; s.map[0][1] = 2; s.map[0][2] = 1;
        s.map[1][0] = 1; s.map[2][2] = 1;
        memset(unit.map,0,sizeof(unit.map));
        for(i = 0; i < 3; i ++)
        unit.map[i][i] = 1;
        n -= 2;
        Matrix();
        __int64 ans = 0;
        for(i = 0; i < 3; i ++)
        ans += unit.map[0][i]*f[2-i], ans %= mod;
        printf("%I64d\n",ans);
    }
    return 0;
}

解题参考:http://blog.csdn.net/jzmzy/article/details/16342515


  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。