HDU 1003 解题报告

问题描述：求最大连续字串

分析：一道简单的DP，状态转移方程是d[i] = ( d[i-1]+a[i] > a[i] ) ? d[i-1]+a[i] : a[i]

d[i]表示以第i个数字结尾的连续字串的最大值，限制条件是 d[0]=0

题目要求找出最大连续字串的首尾序号，尾序号显然是d[i]的下标 i ，首序号用数组start[i]保存，point是保存首序号的临时量，注意point初值是1

还有一点，最后一组数据输出完换行后不能再打印空行，否则会判 Presentation Error

 #include<cstdio>

 int a[],start[],d[],T;

 int main()

 {

     scanf("%d",&T);

     int t=;

     while(++t<=T)

     {

         printf("Case %d:\n",t);

         int n;

         scanf("%d",&n);

         for(int i=;i<=n;i++)

             scanf("%d",&a[i]);

         int point=;

         d[]=;

         for(int i=;i<=n;i++)

         {

             if(d[i-]+a[i]>a[i])

             {

                 d[i]=d[i-]+a[i];

                 start[i]=point;

             }

             else

             {

                 d[i]=a[i];

                 start[i]=point=i;

             }

         }

         int max=d[],ins=;

         for(int i=;i<=n;i++)

         {

             if(d[i]>max)

             {

                 max=d[i];ins=i;

             }

         }

         printf("%d %d %d\n",max,start[ins],ins);

         if(t<T) printf("\n");

     }

 }