4_11.c

求最佳路径：用户输入几条路径的权值

#include "Stdio.h"
#include "Conio.h"
int Max(int a,int b,int c)
{
   int x;
   x=a;
   if(x<b) x=b;
   return(x>c?x:c);
}
int maxsum(int m,int n,int a[])
{
 if(n<m||m<1) return 0;
 int *b=new int [n+1];
 int *c=new int [n+1];
 b[0]=0;
 c[1]=0;
 for(int i=1;i<=m;i++)
 {
  b[i]=b[i-1]+a[i];
  c[i-1]=b[i];
  int max=b[i];
  for(int j=i+1;j<=i+n-m;j++)
  {
      b[j]=b[j-1]>c[j-1]?b[j-1]+a[j]:c[j-1]+a[j];
      c[j-1]=max;
      if(max<b[j]) max=b[j];
  }
  c[i+n-m]=max;
 }
 int sum=0;
 for(int j=m;j<=n;j++)
     if(sum<b[j]) sum=b[j];
 return sum;
}
int main(void)
{
  int i,j,a[5][4],m,n;
  printf("input:");
  for(i=0;i<5;i++)         /*输入数据*/
  {
     for(j=1;j<4;j++)
       scanf("%d",&a[i][j]);
     a[i][0]=Max(a[i][1],a[i][2],a[i][3]);             /*把每一列的最大值放到a[i][0]*/
  }
  printf("1\t2\t3\t4\t5\n");         /*输出数据*/
  for(i=1;i<4;i++)
  {
     for(j=0;j<5;j++)
       printf("%d\t",a[j][i]);
     printf("\n");
  }
  printf("input from where to where:");
  scanf("%d",&m);
  scanf("%d",&n);
  for(i=m-1;i<n-1;i++)        /*输出路径*/
    printf("%d  ",a[i][0]);
  getch();
  return 0;
}