【问题描述】Jill要进行一次旅行，沿途中要经过若干个城市。对于每两个相邻城市之间的路程，他都可以选择骑自选车或是坐公车汽车。如果沿途风景怡人，则他更喜欢骑自选车来完成这段路程。
Jill对每段路程都有评出了一个满意度，这是一个非零整数，所有他喜欢的路程标以正数，不喜欢的路程标以负数，数的绝对值大小代表他喜欢/不喜欢的程度。
如果在本次旅行中只允许在一段连续路程中骑自行车，而剩下的路程都坐公共汽车，并且要求骑车经过的那段路程满意度之和最大，请编程找出这样的路程。
【输入文件】输入文件jill.in第一行是一个整数b（1<=b<=5），代表本文件中提供b组输入数据。每组输入数据代表一次旅行中各相邻城市间路程的满意度，格式如下：
N
a1,2
a2,3
.......
aN-1,N
其中N（2<=N<=2000）是这次旅行中的城市总数，后面的N-1个数值ai,i+1分别表示城市i（1<=i<=N-1）与城市i+1之间路程的满意度。在每个数字之前可能有若干空格。
【输出文件】输出文件为jill.out。你的程序要为每组输入数据计算出骑自行车使满意度最大的连续路程。如果Jill在城市i开始骑自行车，在城市j（j>i）又开始坐公共汽车，那么满意度之和为：
A = ai,i+1 + ai+1, i+2, + ......+ aj-1, j
如果A>0，表示存在满意路径。这时使A达到 最大的路程为所求的解，输出如下内容（其中1<=r<=b是输入数据的序号）：
The nicest part of route r is between stops i and j
如果存在多条路程使其满意度之和都是最大值，则选择路径最长的那一条（即j-I最大者）；如果仍然存在多条这样的路径，则选择最早开始骑自选车的那一条（即i最小者）。
如果不存在这样的路径使A>0，则输出：
Route r has no nice parts
在输出的每一行末尾都要有一个回车符。
【输入样例】
3
3
-1
6
10
4
-5
4
-3
4
4
-4
4
-5
4
-2
-3
-4
【输出样例】
The nicest part of route 1 is between stops 2 and 3
The nicest part of route 2 is between stops 3 and 9
Route 3 has no nice parts
【样例说明】 第一组的满意路径是从2到3，第二组的满意路径是从3到9，最后一组没有满意路径。
【评分标准】 结果正确则该测试点得满分，否则该测试点得0分。上传c语言源程序为jill.c。
#include <iostream>
using namespace std;
#include <fstream>
/*
输入城市数目 n
对应的路径条数有 n-1 条
题目求解最优的骑行路径
*/
int main() {
fstream filein;
fstream fileout;
filein.open("jill.in", ios::in);
fileout.open("jill.out", ios::out);
int result_road[128][3]; // 3 列 第一列表示数据组号 第二列表示 起点 第三列表示终点
int length_result = 0;
int road[128]; // 存放路径的兴趣度
int account;
filein >> account; //输入数据组的个数
while (account) {
int city_num;
filein >> city_num; //输入城市的个数
for (int i = 0; i < city_num - 1; i++) {
filein >> road[i];
}
int max = 0; //定义最大满意度
int start = 0; //定义起点
int end = 0; //定义终点
for (int i = 0; i < city_num - 1; i++) { // 假设每一点都是起点
if (road[i] < 0) {
continue;
}
for (int h = city_num - 2; h >= i; h--) { //假设每一点都是终点
if (road[h] < 0) {
continue;
}
int temp = 0;
for (int w = i; w <= h; w++) {
temp += road[w];
}
if (temp > max) {
max = temp;
start = i + 1;
end = h + 2;
}
}
// cout << "---" << max << "---";
}
result_road[length_result][0] = max;
result_road[length_result][1] = start;
result_road[length_result++][2] = end;
account--;
}
for (int i = 0; i < length_result; i++) {
if (result_road[i][0] <= 0) {
fileout << "Route " << i + 1 << " has no nice parts" << endl;
} else {
fileout << "The nicest part of route " << i + 1 << " is between stops " << result_road[i][1] << " and " <<
result_road[i][2] << endl;
}
}
}