杭電1003 Max Sum(dp)

1379 ワード

前のブログで少し問題がありました.
正確にはoj存愛欠陥でしょう.具体的には、
eg:5 0 0 0 0 0 0と入力します.
出力:0 1 5
しかし、前のコードはすでにAです.正しい出力は:0 1
問題の中でIf there are more than one result,output the first oneと言いました.
この問題はdpで解決できます.コードは次のとおりです.
#include <stdio.h>
int main()
{
    int i,j,x,n,m,sum,max;
    int start,end,nowstart;
    scanf("%d",&n);
    {
        for (i=1;i<=n;i++)
        {
            scanf("%d%d",&m,&x);
            sum=max=x;
            start=end=nowstart=1;
            for (j=2;j<=m;j++)
            {
                scanf("%d",&x);
                if (sum+x<x)
                {
                    sum=x;
                    nowstart=j;
                }
                else
                {
                    sum+=x;
                    //end=j;
                    /**If there are more than one result,
                    output the first one.!!!!!!!!**/
                }
                if (sum>max)
                {
                    max=sum;
                    start=nowstart;
                    end=j;
                }
            }
            printf("Case %d:
",i); printf("%d %d %d
",max,start,end); if (i!=n) { printf("
"); } } } return 0; }