采用DP。当前的数字，要么加在之前的若干个数字的后面，要么另外成为一个序列的开头；具体是如何决策，需要比较当前数字t与之前若干数字的和sum的大小。
以下是我的代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int kInf (200000000);
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int T;
cin>>T;
for(int k=1;k<=T;k++)
{
int n;
int sum(-kInf),now_left(0),now_right(0);
int ans_value(-kInf),ans_left(now_left),ans_right(now_right);
cin>>n;
for(int i=1;i<=n;i++)
{
int t;
cin>>t;
if(sum+t<t)
{
sum=t;
now_left=now_right=i;
}
else if(sum+t==t)
{
sum=t;
now_right++;
}
else if(sum+t>t)
{
sum+=t;
now_right++;
}
if(ans_value<sum || (ans_value==sum && ans_left>now_left) || (ans_value==sum && ans_left==now_left && ans_right>now_right))
{
ans_value=sum;
ans_left=now_left;
ans_right=now_right;
}
}
if(k!=1) cout<<endl;
cout<<"Case "<<k<<":"<<endl;
cout<<ans_value<<" "<<ans_left<<" "<<ans_right<<endl;
}
return 0;
}
posted on 2011-03-10 22:03
lee1r 阅读(634)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划