这个是在论坛里看到的。。。盯了一下午了。。。什么都么盯出来。。

#include "stdio.h"
#define N 100000
int main()
{
        long n,i,j,a[N]={0},b[N]={0},Mt,Max,temp;
         while(scanf("%d",&n)!=EOF)
         {
                         Max=0;
                         for(i=1;i<=n;i++)
          {
             for(j=1;j<=i;j++)
                         scanf("%ld",&a[j]);
                            a[j]=0;
                if(i==1)
                                {
                            for(j=1;j<=i;j++)
                                        {
                                       b[j]=a[j];
                                        Max=b[j];
                                        }
                                         b[j]=0;
                                }
                 else
                 {
                         Mt=0;
                         for(j=1;j<=i;j++)
                         {
                            temp=b[j];
                            if(b[j]>Mt) Mt=b[j];
                            b[j]=Mt+a[j];
                            if(b[j]>Max) Max=b[j];
                            Mt=temp;
                                                 }
                                                 b[j]=0;
                 }           }
     printf("It will take him %ld steps!\n",Max);
   
        }
         return 0;
}
红色的地方我绕啊绕绕不出来了。。。。大家帮帮忙。。。我盯的眼睛都直了
原题是：
goldfisher为了解救被绑架的未婚妻而来到了恶魔岛。上岛前，一个神秘的印度人yingnan告诉他恶魔岛处处布满陷阱，只有沿着地上标记数字和为最大的路径才能找到公主。为此他给goldfisher画了一个草图，假使地上标记的数字如下：
   1
  2 3
.1 5 9
9 1 1 1
其中的最大路径是1-3-9-1，最大的和是14，只有沿着这条路径走，才能找到公主。goldfisher犯难了，因为现实中标记的数字更多，难度更大。你能帮助goldfisher找到正确的道路解救他的未婚妻吗？
是在论坛里看到的。。。。
----------------解决方案--------------------------------------------------------
题目在哪?
最佳核心算法:DP
----------------解决方案--------------------------------------------------------
回楼上，题目在http://yzfy.org/bbs/viewthread.php?tid=34

[[it] 本帖最后由 雨中飞燕 于 2008-1-30 20:06 编辑 [/it]]
----------------解决方案--------------------------------------------------------
#include<stdio.h>
#include<conio.h>
int max(int r,int t)
{
    if(r>t) return r;
    else return t;
}
int main(void)
{
    int i,j;
    int n;
    int temp;
    int line[100001]={0};
    scanf("%d",&n);
    for(i=1;i<=n;i++)
       for(j=i;j>0;j--)
      {
        scanf("%d",&temp);
        line[j]=max(line[j],line[j-1])+temp;
      }
    temp=0;
    for(i=1;i<=n;i++) temp=max(temp,line[i]);
    printf("%d\n",temp);
    getch(); /*测评时去掉*/
    return 0;
}

[[it] 本帖最后由 卧龙孔明 于 2008-1-30 20:50 编辑 [/it]]
----------------解决方案--------------------------------------------------------
去看了看才知道,N<=100
以上程序中将1000001改成101就可以了,否则memset用时巨大
#include<stdio.h>
#include<string.h>
int max(int r,int t)
{
    if(r>t) return r;
    else return t;
}
int main(void)
{
    int i,j;
    int n;
    int temp;
    int line[101]={0};
    while(scanf("%d",&n)!=EOF)
    {
      memset(line,0,sizeof(line));
      for(i=1;i<=n;i++)
        for(j=i;j>0;j--)
        {
          scanf("%d",&temp);
          line[j]=max(line[j],line[j-1])+temp;
        }
      temp=0;
      for(i=1;i<=n;i++) if(temp<line[i]) temp=line[i];
      printf("It will take him %d steps!\n",temp);
    }
    return 0;
}
----------------解决方案--------------------------------------------------------