跳至正文

USACO 1.5.1 Number Triangles

  • OI路程

  明显是一个动态规划,有两种思路,一种是至上而下的,一种是至下而上的,让我联想到了几个大国家的革命和改革,我支持改革,革命总是要留下一些历史痕迹,漏洞,所以我选择的是至下而上的改革。至下而上的DP有什么好处呢?好处多了,因为没有任何特殊情况要考虑,如果是至上而下的DP的话,首先有特殊情况,对于每一个内层循环的值等于外层的值的话,但是这个处理得好的话还是可以做到不要多余的if来判断i是否等于j,在输出答案时不需要遍历底层,在这里的代码我犯了一个小错误导致我的代码丢了最后一个点。
  犯的错误:数组的下标使用错误了,在极限值(1000)时会溢出!
  提交了两次,代码如下:

/
LANG: C
ID: yylogoo2
PROG: numtri
/
#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int f[1000][1000];
int n;

int main(void)
{
        int i, j;
        freopen("numtri.in""r"stdin);
        freopen("numtri.out""w"stdout);
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                for(j = 0; j <= i; j++){
                        scanf("%d", &f[i][j]);
                }
        }
        /
        Mistack 1:
          下面的i我写的是i–, 因为前面的代码. 但是删掉之后忘记修改这里了,
        i要从n – 2开始枚举..
        
/
        for(i = n – 2; i >= 0; i–){
                for(j = 0; j <= i; j++){
                        f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
                }
        }
        printf("%d\n", f[0][0]);
        return 0;
}

发表回复

您的电子邮箱地址不会被公开。