题意:连续序列和最大，直接枚举。。。。。
代码跑了2.4s.QAQ
#include <string>
#include<iostream>
#include<map>
#include<memory.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<math.h>
#include<iomanip>
#include<bitset>
#include"math.h"
namespace cc
{
using std::cout;
using std::endl;
using std::cin;
using std::map;
using std::vector;
using std::string;
using std::sort;
using std::priority_queue;
using std::greater;
using std::vector;
using std::swap;
using std::stack;
using std::queue;
using std::bitset; constexpr int N = ;
int seg[N] = { };
void solve()
{
int n;
cin >> n;
int t;
int cases = ;
while (n--)
{
cin >> t;
--t;
for (int i=;i<t;i++)
cin >> seg[i];
int as=-, ae=-;
int amax = -;
for (int s=;s<t;s++)
{
int curMax = ;
for (int e=s;e < t;e++)
{
curMax += seg[e];
if (curMax > amax)
{
amax = curMax;
as = s+;
ae = e+;
}
else if (curMax == amax&& as!=-)
{
if (ae - as- < e - s)
{
as = s+;
ae = e+;
}
}
} }
if (as==-)
{ cout << "Route "<<cases<<" has no nice parts" << endl;
}
else
{
cout<<"The nicest part of route "<<cases <<" is between stops "<<as<<" and "<<ae<<endl;
}
cases++; } }
}; int main()
{ #ifndef ONLINE_JUDGE
freopen("d://1.text", "r", stdin);
#endif // !ONLINE_JUDGE
cc::solve(); return ;
}
下面这个代码只花了120ms.
再次叙述题意：对于一个连续序列，寻找连续和最大的开始下标和结束下标，如果有多最大和相等，寻找最长的，如果最长的一样，寻找开始小标最小的.
以下代码只用了一层循环。使用as和ae标识我们期望的结果下标.sum表示当前的和,s表示当期和开始的计算下标.
#include"pch.h"
#include <string>
#include<iostream>
#include<map>
#include<memory.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<math.h>
#include<iomanip>
#include<bitset>
#include"math.h"
namespace cc
{
using std::cout;
using std::endl;
using std::cin;
using std::map;
using std::vector;
using std::string;
using std::sort;
using std::priority_queue;
using std::greater;
using std::vector;
using std::swap;
using std::stack;
using std::queue;
using std::bitset; void solve()
{
int n;
cin >> n;
int t;
int cases = ;
while (n--)
{
cin >> t;
int as = , ae = ;
int s = ;
int ans = -;
int sum = ;
for (int i = ;i < t;i++)
{
int k;
cin >> k;
sum += k;
if (sum > ans || (sum == ans && (ae - as) < (i - s)))
{
ans = sum;
as = s;
ae = i;
}
if (sum < )
{
sum = ;
s = i + ;
}
}
if (ans <= )
{
cout << "Route " << cases << " has no nice parts" << endl;
}
else
{
cout << "The nicest part of route " << cases
<< " is between stops " << as << " and " << ae+ << endl;
}
++cases;
} }
}; int main()
{ #ifndef ONLINE_JUDGE
freopen("d://1.text", "r", stdin);
#endif // !ONLINE_JUDGE
cc::solve(); return ;
}