USACO —— numtri

Published on 2010 / 03 / 31

解题思路：

两层搜索，用滚动数组可以节省空间。

递归方程：

Floor[Now][site]=Num[site]+Max(Floor[Last][site]，Floor[Last][site-1])；

耗时情况：

Test 1: TEST OK [0.011 secs, 1916 KB]
Test 2: TEST OK [0.000 secs, 1916 KB]
Test 3: TEST OK [0.011 secs, 1916 KB]
Test 4: TEST OK [0.011 secs, 1916 KB]
Test 5: TEST OK [0.000 secs, 1916 KB]
Test 6: TEST OK [0.022 secs, 1916 KB]
Test 7: TEST OK [0.011 secs, 1916 KB]
Test 8: TEST OK [0.022 secs, 1916 KB]
Test 9: TEST OK [0.259 secs, 1916 KB]

我的代码：

/*
ID: 
PROG: numtri
LANG: C
*/

#include<stdio.h>

int R, Num[2][1001], Floor[1001];

int main() {
    FILE *fs, *fp;
    fs = fopen("numtri.in", "r");
    fp = fopen("numtri.out", "w");
    fscanf(fs, "%d", &R);
    int a, b, c, floor = 1;
    int now, last;
    while (floor <= R) {
        now = floor % 2;
        last = (floor + 1) % 2;

        for (a = 1; a <= floor; a++)
            fscanf(fs, "%d", &Floor[a]);

        for (a = 1; a <= floor; a++) {
            Num[now][a] = Num[last][a] > Num[last][a - 1] ? Num[last][a] : Num[last][a - 1];
            Num[now][a] += Floor[a];
        }
        floor++;
    }
    for (a = 1, b = R % 2, c = 0; a <= R; a++)
        if (c < Num[b][a])
            c = Num[b][a];
    fprintf(fp, "%d\n", c);
    fclose(fs);
    fclose(fp);
    return 0;
}