posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

USACO 1.1.5 Number Triangles

Posted on 2007-06-01 21:51 ZelluX 阅读(258) 评论(0)  编辑  收藏 所属分类: Algorithm
最简单的DP，于是只用了一维数组稍微提高下难度，不过还是一次编译一次提交成功了，恩

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

#include <iostream>
#include <fstream>

using namespace std;

int main() {
    ifstream fin("numtri.in");
    ofstream fout("numtri.out");
    int n;
    fin >> n;
    int i, j;
    int f[1001];
    for (i = 0; i <= n; i++) {
        f[i] = 0;
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j <= i; j++) {
            int x;
            fin >> x;
            f[j] += x;
        }
        int temp[1001];
        for (j = 0; j <= i; j++) {
            temp[j] = f[j];
        }
        temp[i + 1] = f[i];
        for (j = 0; j <= i; j++) {
            if (f[j] > temp[j + 1]) {
                temp[j + 1] = f[j];
            }
        }
        for (j = 0; j <= i + 1; j++) {
            f[j] = temp[j];
        }
    }

    int max = 0;
    for (i = 0; i <= n; i++) {
        if (f[i] > max) {
            max = f[i];
        }
    }
    fout << max << endl;
    return 0;
}

只有注册用户登录后才能发表评论。
网站导航: