C語言：一個簡單的online judge問題

經(jīng)過目測，應(yīng)該是dp

這是一道動態(tài)規(guī)劃的問題，而你使用了貪心算法
使用一個簡單的樣例來反駁：

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) //找數(shù)組里最大的元素
{
  int res = f[1];
  for (int i = 2; i <= n; i++)
    res = (res <= f[i] ? f[i] : res);
  return res;
}

int main()
{
  int t; //循環(huán)次數(shù)
  scanf("%d", &t);
  int n; //三角形層數(shù)
  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]; //動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程核心
      }
      //交換pfa和pfb的地位，用于節(jié)省空間
      swap = pfa;
      pfa = pfb;
      pfb = swap;
    }
    printf("%d\n", find(pfb, 2 * n - 1)); //在最后一行里尋找最大的元素，該元素即為結(jié)果
  }
  return 0; 
}

時間復(fù)雜度：t * (n*n*3 + n) => O(n^2)
我的代碼中如何節(jié)省空間（交替使用兩個一維數(shù)組）的部分并不重要，請仔細思考以下部分：

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的越界)

請拿出筆和紙，隨便找一組數(shù)據(jù)，模擬一下。注意這里是直角三角形，不是等腰三角形:)

問題很多，而且你的代碼并沒有達到要求。這個題是要你做樹形檢索，不是找每行的最大值。

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

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


int main()
{
    int t; //定義一個自然數(shù)t，代表將要測試數(shù)據(jù)的組數(shù)
    scanf_s("%d", &t);
    while (t--)
    {
        int n, sum = 0, i, j;
        scanf_s("%d", &n);    //輸入每一組測試數(shù)據(jù)（三角形）的行數(shù)
        if (n == 1)
        {
            int num;
            scanf_s("%d", &num);
            sum += num;
        }        //如果只有一行，直接加上輸入的一個數(shù)
        else {            //如果不止一行
            int flag = 0;  // ---> flag每層循環(huán)都未初始化，上層的flag傳到下層去了，不知道你這個flag要干什么
            for (i = 1;i <= n;i++)
            {
                int max = 0;
                int *a = (int *)malloc(sizeof(int)*(2 * i - 1));    //每行的數(shù)據(jù)個數(shù)為此行的行數(shù)乘2再減1，那么每跳到一行就定義一個能容納那么多數(shù)的數(shù)組
                for (j = 0;j<2 * i - 1;j++)
                {
                    scanf_s("%d", &a[j]);   //輸入2*i-1個數(shù)
                }
                if (i <= 2)      //如果行數(shù)在1和2之間，找出每行的最大值，并加到計數(shù)器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  //當行數(shù)在兩行以上
                {
                    int m;
                    int flag1;  //定義一個flag1來更新從第三行開始最大值的位置 ---> flag1未賦值，如果你后面的for循環(huán)里的if從未執(zhí)行過，你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;
}