首页 > ACM题库 > HDU-杭电 > HDU 2930-Collapse!!-分治-[解题报告]HOJ
2014
02-23

HDU 2930-Collapse!!-分治-[解题报告]HOJ

Collapse!!

问题描述 :

Candy and his friends found a treasure map. With the help of the map, they successfully found the treasure inside an ancient cave, but just as they took the large treasure box, the cave started to collapse! Candy must find a way out, but the rocks are falling down so quickly that it’s impossible to run out with bare feet. After carefully examined the treasure box, they found a digit panel, a button, and a small piece of paper. "I am not an ordinary treasure box, I am a mini-spaceship, your last hope to escape. Use the digit panel to setup my speed, then press the button to launch. I’ll fly from left to right, until I reach the exit. The trouble is: I am very weak. I’ll explode immediately when hit by any falling rock, but if I’m just touching one, it’s ok. When flying, I burn the treasures inside. The higher my speed is, the more treasures I will burn. Thus, be sure to find an appropriate speed before starting your journey. The last thing you need to know is: don’t be too slow. The exit will be blocked after a while."

Fig 1. Collision between the spaceship and a rock A list of rocks that will fall down is enclosed in that piece of paper. All the rocks have the same speed. Each rock continues to fall down until its topmost point reaches the land (i.e. y = 0).You can start your journey at any time, but once you launch the spaceship, it never stops before reaching the exit or being destroyed!
Write a program to find the minimal speed that takes you out of the cave.

输入:

The input contains several test cases. The first line of each case contains seven positive integers n, a, b, L, H, V, T (1 ≤ n ≤ 50, 1 ≤ a, b ≤ 10, 1 ≤ L, H, V, T ≤ 10000). The spaceship is a units wide and b units high. Its bottom-left corner is initially (i.e. at time 0) at (0, 0). When the bottom-left corner reaches (L, 0) before time T, you succeeded. The height of the cave is H. The speed of each rock is V. There are n lines followed. Each of these lines contains three integers x, r, t (1 ≤ t ≤ T, 1 ≤ r ≤ 200, a + r ≤ x ≤ L – r, b < H – r): at time t, there will be a falling rock with a radius of r with its center at (x, H). The descriptions of rocks are sorted in increasing order of falling time. The last test case is followed by a single zero, which should not be processed.

输出:

The input contains several test cases. The first line of each case contains seven positive integers n, a, b, L, H, V, T (1 ≤ n ≤ 50, 1 ≤ a, b ≤ 10, 1 ≤ L, H, V, T ≤ 10000). The spaceship is a units wide and b units high. Its bottom-left corner is initially (i.e. at time 0) at (0, 0). When the bottom-left corner reaches (L, 0) before time T, you succeeded. The height of the cave is H. The speed of each rock is V. There are n lines followed. Each of these lines contains three integers x, r, t (1 ≤ t ≤ T, 1 ≤ r ≤ 200, a + r ≤ x ≤ L – r, b < H – r): at time t, there will be a falling rock with a radius of r with its center at (x, H). The descriptions of rocks are sorted in increasing order of falling time. The last test case is followed by a single zero, which should not be processed.

样例输入:

1 2 1 20 12 3 20
5 2 5
0

样例输出:

Case 1: 1.00

题目链接:http://acm.hit.edu.cn/hoj/problem/view?id=2930

本题是处理线性递推。

递推式:f[i] = 2*f[i-1] + f[i-3];

求线性递推问题可以转换为矩阵运算:

出任何一个线性递推式的第n项,其对应矩阵的构造方法为:在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1,矩阵第n行填对应的系数,其它地方都填0。例如,我们可以用下面的矩阵乘法来二分计算f(n) = 4f(n-1) – 3f(n-2) + 2f(n-4)的第k项:

a,b,c,d的顺序为项数的从低到高。

对于本题的递推式,f[i] = 2*f[i-1] + f[i-3];

我们可以构造连乘矩阵:

A= [0 1 0

0 0 1

1 0 2],

B = [f[0]

f[1]

f[2]]

则第n项f[n] = A^(n-2) * B.

另外用到矩阵的快速幂运算,用二分法就行了。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define max 3
struct Matrix
{
    int data[max][max];
};

Matrix A,B;
int n = 3;
int mod = 2010;

void init()
{
    memset(A.data,0,sizeof(A.data));
    memset(B.data,0,sizeof(B.data));
    A.data[0][1] = 1;
    A.data[1][2] = 1;
    A.data[2][0] = 1;
    A.data[2][2] = 2;
    B.data[0][0] = 1;
    B.data[1][0] = 1;
    B.data[2][0] = 2;
}
//矩阵相乘
Matrix mul(Matrix u,Matrix v)
{
    Matrix t;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            t.data[i][j] = 0;
            for(int k=0;k<n;k++)
            {
                t.data[i][j] += (u.data[i][k] * v.data[k][j])%mod;
                t.data[i][j] %= mod;
            }
        }
    }
    return t;
}
//矩阵的幂
Matrix power(Matrix matrix,int k)
{
    int k_temp = k;
    Matrix result,a;

    memset(result.data,0,sizeof(result.data));

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            a.data[i][j] = matrix.data[i][j];
            if(i == j)
            {
                result.data[i][j] = 1;
            }
            //printf("%d ",a.data[i][j]);
        }
        //printf("\n");
    }
    while(k_temp)
    {
        if(k_temp&1)
        {
            result = mul(result,a);
        }
        a = mul(a,a);
        k_temp = k_temp>>1;
    }
    return result;

}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int num;
    init();
    while(scanf(" %d",&num)!=EOF)
    {
        if(num == 1) printf("1\n");
        else if(num == 2) printf("2\n");
        else
        {
            Matrix temp = power(A,num - 2);
            Matrix fin = mul(temp,B);
            printf("%d\n",fin.data[2][0]);
        }
    }
    return 0;
}

解题参考:http://blog.csdn.net/niuox/article/details/8804652


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  3. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。