模拟递归问题。直接递归肯定不行，最容易想到的方法就是用数组模拟。中途遇到了一个问题，就是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;
}

• Relative Posts