C语言：一个简单的online judge问题

Question

第一行，一个自然数T，表示总共给出的三角形数，对于每一个三角形，首先给出一个自然数n，表示将输入的三角形有n行。接下来有n行，第i行有2i-1个数字，

要求你用笔从第1行画到第n（0 < n ≤ 100）行，从当前行往下画的时候只能在相邻的数字经过，也就是说，如果从一行的一个数往下画，只能选择其左下或者正下或者右下三个数中的一个（如果存在的话），把所有被画起来的数字相加，得到一个和，求能得到的最大的和的值是多少。
上例中能得到的最大的和为3 + 7 + 4 + 9 = 23.

测试样例：

对于图上的测试样例，我的代码可以完全通过。但是为了保险，我自己又添加了几组测试数据，出现了问题：

如果测试两组数据，也就是这样：

<PS:这是ide的运行窗口，白色的数字代表每组测试数据得出的结果。另外，黑色图中第二组是我自己添加的测试数据，也就是下面这组：>

是的，目前看来没问题，但是让我们将测试数据增加到三组————也就是Sample input的数据再加上我自己添加的一组数据，出问题了：

然而，再单独运行我添加的一组数据，结果又正确了：

下面先贴上代码：

#include <stdio.h>
int main()
{
    int t; //定义一个自然数t，代表将要测试数据的组数
    scanf("%d",&t);
    while(t --)
    {
        int n,sum = 0,i,j;
        scanf("%d",&n);    //输入每一组测试数据（三角形）的行数
        if(n==1)        
        {
            int num;
            scanf("%d",&num);
            sum += num;
        }        //如果只有一行，直接加上输入的一个数
        else{            //如果不止一行
            int flag = 0;
            for(i=1;i<=n;i++)
            {
                int max = 0;
                int a[2*i-1];    //每行的数据个数为此行的行数乘2再减1，那么每跳到一行就定义一个能容纳那么多数的数组
                for(j=0;j<2*i-1;j++)
                {
                    scanf("%d",&a[j]);   //输入2*i-1个数
                }
                if(i<=2)      //如果行数在1和2之间，找出每行的最大值，并加到计数器sum上，知道加完第二行，用flag记录第二行最大值的位置
                {
                    int k;
                    max = a[0];
                    for(k=0;k<2*i-1;k++)
                    {
                        if(a[k]>max){
                            max = a[k];
                            flag = k;
                        }
                    }
                    sum+=max;
                }
                else  //当行数在两行以上
                {
                    int m;
                    int flag1;  //定义一个flag1来更新从第三行开始最大值的位置
                    max = a[flag];
                    for(m=flag;m<=flag+2;m++)   
                    {
                        if(a[m]>max){
                            max = a[m];
                            flag1 = m;
                        }
                    }
                    sum += max;
                    flag = flag1;
                }
            }
        }
        printf("%d\n",sum);
    }
}

花了一个晚自习也没有debug出来，我快疯了.........

Answer 1

这是一道动态规划的问题，而你使用了贪心算法
使用一个简单的样例来反驳：

1
1
1 0 -1
0 0 0 0 10000

大概不用解释了....

#include <stdio.h>
#include <limits.h>

int a[101];
int fa[101];
int fb[101];

int max(const int f[], int i, int j) //找出可到达(i,j)的最大元素
{
  int res = INT_MIN; //负极大
  for (int k = -2; k <= 0; k++)
  {
    if ((j + k) < 1 || (j + k) > 2 * (i - 1) - 1) continue; //处理越界
    res = (res <= f[j + k] ? f[j + k] : res); //找到最大的元素
  }
  return res;
}

int find(const int f[], int n) //找数组里最大的元素
{
  int res = f[1];
  for (int i = 2; i <= n; i++)
    res = (res <= f[i] ? f[i] : res);
  return res;
}

int main()
{
  int t; //循环次数
  scanf("%d", &t);
  int n; //三角形层数
  int *pfa; //指向当前行的指针
  int *pfb; //指向上一行的指针
  int *swap; //用于交换的指针
  while (t--)
  {
    scanf("%d", &n);
    scanf("%d", &a[1]);
    pfa = fa;
    pfb = fb;
    pfb[1] = a[1]; //一开始就从第二行开始处理，所以第一行用pfb指向
    for (int i = 2; i <= n; i++)
    {
      for (int j = 1; j <= 2 * i - 1; j++)
      {
        scanf("%d", &a[i]);
        pfa[j] = max(pfb, i, j) + a[i]; //动态规划状态转移方程核心
      }
      //交换pfa和pfb的地位，用于节省空间
      swap = pfa;
      pfa = pfb;
      pfb = swap;
    }
    printf("%d\n", find(pfb, 2 * n - 1)); //在最后一行里寻找最大的元素，该元素即为结果
  }
  return 0; 
}

时间复杂度：t * (n*n*3 + n) => O(n^2)
我的代码中如何节省空间（交替使用两个一维数组）的部分并不重要，请仔细思考以下部分：

f[1][1] = a[1][1];
f[i][j] = max(f[i-1][j+k]) + a[i][j]    2<=i<=n, 1<=j<=2*i-1, -2<=k<=0 (注意处理j+k的越界)

请拿出笔和纸，随便找一组数据，模拟一下。注意这里是直角三角形，不是等腰三角形:)

Answer 2

问题很多，而且你的代码并没有达到要求。这个题是要你做树形检索，不是找每行的最大值。

// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>


int main()
{
    int t; //定义一个自然数t，代表将要测试数据的组数
    scanf_s("%d", &t);
    while (t--)
    {
        int n, sum = 0, i, j;
        scanf_s("%d", &n);    //输入每一组测试数据（三角形）的行数
        if (n == 1)
        {
            int num;
            scanf_s("%d", &num);
            sum += num;
        }        //如果只有一行，直接加上输入的一个数
        else {            //如果不止一行
            int flag = 0;  // ---> flag每层循环都未初始化，上层的flag传到下层去了，不知道你这个flag要干什么
            for (i = 1;i <= n;i++)
            {
                int max = 0;
                int *a = (int *)malloc(sizeof(int)*(2 * i - 1));    //每行的数据个数为此行的行数乘2再减1，那么每跳到一行就定义一个能容纳那么多数的数组
                for (j = 0;j<2 * i - 1;j++)
                {
                    scanf_s("%d", &a[j]);   //输入2*i-1个数
                }
                if (i <= 2)      //如果行数在1和2之间，找出每行的最大值，并加到计数器sum上，知道加完第二行，用flag记录第二行最大值的位置
                {
                    int k;
                    max = a[0];
                    for (k = 0;k<2 * i - 1;k++)
                    {
                        if (a[k]>max) {
                            max = a[k];
                            flag = k;
                        }
                    }
                    sum += max;
                }
                else  //当行数在两行以上
                {
                    int m;
                    int flag1;  //定义一个flag1来更新从第三行开始最大值的位置 ---> flag1未赋值，如果你后面的for循环里的if从未执行过，你flag = flag1一定崩溃
                    max = a[flag];
                    for (m = flag;m <= flag + 2;m++)
                    {
                        if (a[m]>max) {
                            max = a[m];
                            flag1 = m;
                        }
                    }
                    sum += max;
                    flag = flag1;
                }
                free(a);
                a = NULL;
            }
        }
        printf("%d\n", sum);
    }
    getchar();
    return 0;
}

Answer 3

经过目测，应该是dp