zoj 1168 - 行者无疆 始于足下 - 行走,思考,在路上

zoj 1168

xiaohanyu posted @ Thu, 20 May 2010 03:18:25 +0800 in Algorithm with tags ZOJ STL c++ , 1695 readers

模拟递归问题。直接递归肯定不行,最容易想到的方法就是用数组模拟。中途遇到了一个问题,就是c++ iostream库的效率问题。用cin >> a >> b >> c时,TLE;换成scanf("%d%d%d", &a, &b, &c)时,AC,时间80ms。status中最前面的都是60ms,看来优化空间不大。关于c库和c++库的输入输出,还有待研

/**
 * @file   zoj1168.c
 * @author  <lox@freelox>
 * @date   Wed May 19 18:59:59 2010
 * 
 * @brief  zoj1168, 模拟问题。直接查表解决。
 * 但是需要注意的是,此题目用scanf系列,AC,时间80ms,用c++的cin流,则TLE,
 * 莫非cin和scanf真有那么大的时间消耗差别?
 */


#include <stdio.h>

int main(int argc, char *argv[])
{
    int w[21][21][21];

    int a, b, c;
    
    for (a = 0; a <= 20; a++)
    {
        for (b = 0; b <= 20; b++)
        {
            for (c = 0; c <= 20; c++)
            {
                if (a == 0 || b == 0 || c == 0)
                {
                    w[a][b][c] = 1;
                }
                else if (a < b && b < c)
                {
                    w[a][b][c] = w[a][b][c-1] + w[a][b-1][c-1] - w[a][b-1][c];
                }
                else
                    w[a][b][c] = w[a-1][b][c] + w[a-1][b-1][c] + w[a-1][b][c-1] - w[a-1][b-1][c-1];
            }
        }
    }

    while (scanf("%d%d%d", &a, &b, &c))
    {
        if (a == -1 && b == -1 && c == -1)
        {
            return 0;
        }
        if (a <= 0 || b <= 0 || c <= 0)
        {
            printf("w(%d, %d, %d) = %d\n",a,b,c,w[0][0][0]);
        }
        else if (a > 20 || b > 20 || c > 20)
        {
            printf("w(%d, %d, %d) = %d\n",a,b,c,w[20][20][20]);
        }
        else
            printf("w(%d, %d, %d) = %d\n",a,b,c,w[a][b][c]);
    }
    
    return 0;
}

Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee