杭電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で解決できます.コードは次のとおりです.
正確には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;
}