采用DP。當(dāng)前的數(shù)字，要么加在之前的若干個數(shù)字的后面，要么另外成為一個序列的開頭；具體是如何決策，需要比較當(dāng)前數(shù)字t與之前若干數(shù)字的和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 閱讀(662)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃