P1216 数字三角形

本文最后修改于 761 天前，部分内容可能已经过时！

最近在学dp，于是选了这一题。这题暴力似乎也能打，但还没打（估计是咕咕咕了），既能练dp还能练dfs，岂不美哉？

P1216 [USACO1.5]数字三角形 Number Triangles

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

         7 
      3   8 
    8   1   0 
  2   7   4   4 
4   5   2   6   5

在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大

输入输出格式

输入格式：

第一个行包含 R(1<= R<=1000) ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。

输出格式：

单独的一行,包含那个可能得到的最大的和。

输入输出样例

输入样例#1：

输出样例#1：

说明

题目翻译来自NOCOW。

USACO Training Section 1.5

解题

7-3-8-7-5 求和是30

方法1：递归枚举暴力

每一条路径都走一遍。
dfs(1,1,7)->dfs(2,1,7)->dfs(2,2,7)->dfs(3,1,10)->……->dfs(n,1,sum)
比较最大值，存入answer。

方法2：dp

瞎推了一包东西，然后发现了什么

                7 
              3   8 
            8   1   0 
          2   7   4   4 
        4   5   2   6   5 
        0    0    0    0    7    0    0
        0    0    0    10    15    0    0
        0    0    18    11    16    0    0
        0    20    25    20    19    0    0
        24    30    22    26    24    0    0
        a[n]={7,10,15,18,11,16,20,25,20,19,24,30,22,26,24}

先读入一组数据，再求和，取最大值。
试了下写比大小，发现并不能写出来，这里max还是伪代码，没有实际作用

    #include <bits/stdc++.h>
    using namespace std;
    int n,m,a[1002],result=0;
    int main() {
        scanf("%d",&n);
        for (int i=n;i;i--) //5->1 共5层 
            for (int j=i;j<=n;j++) {  //
                scanf("%d",&m);
                a[j]=max(a[j+1],a[j])+m;    //dp 找最大 每次读入都将上一层的数据和求和 
            }
        for (int i=0;i<=n;i++) 
            result=max(result,a[i]);
        printf("%d",result);
        return 0;
    }

然后参考题解，发现了这个：

    int max(int &x,int &y){return x>y?x:y;}

我佛了！！！！！！不知道哪里挂了！！！！！！

    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        int n,m,a[1002],result=0;
        scanf("%d",&n);
        for (int i=n;i>=1;i--) //5->1 共5层 
            for (int j=i;j<=n;j++) {  //从i到n，读入n-i次
                scanf("%d",&m);
                a[j]=max(a[j+1],a[j])+m;    //dp 找最大 每次读入都将上一层的数据和求和 
            }
        for (int i=0;i<=n;i++) 
            result=max(result,a[i]);
        printf("%d",result); 
        return 0;
    }

啊啊啊啊啊
然后试了下memset，发现并没有用
玄学错误
11:55分清醒过来了
然后

MD这是大忌啊 int怎么能放在里面呢？？？

同样一个INT类型定义在main函数里和main函数外面有什么区别

    #include <bits/stdc++.h>
    using namespace std;
    int max(int &x,int &y){return x>y?x:y;}
    int n,m,a[1002],result=0;
    int main() {
        scanf("%d",&n);
        for (int i=n;i;i--) //5->1 共5层 
            for (int j=i;j<=n;j++) {  //
                scanf("%d",&m);
                a[j]=max(a[j+1],a[j])+m;    //dp 找最大 每次读入都将上一层的数据和求和 
            }
        for (int i=0;i<=n;i++) 
            result=max(result,a[i]);
        printf("%d",result);
        return 0;
    }

然后...过了

后记

还是要提高码力...我太弱了...
物理已经让我心力交瘁，现在不知道能不能救得过来，救不过来就只能学文了...
还是得拿出时间写题