Q - Jill Rides Again
//
// Q - Jill Rides Again
// #include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;// 2 ≤ s ≤ 20,000
const int MAXN=2e4+5;
int a[MAXN],dp[MAXN];int main()
{// t 条路 每条路有 n 个站台 n-1 个 nice 值// i,j 动态规划 探索路径// x,y 保存最优路径int t,n,i,j,x,y,length_max,cnt=1;scanf("%d",&t);while( t-- ){// nice 值从下标 1 开始读入 取前站台对应每个 nice 值 memset( a,0,sizeof( a ) ); memset( dp,0,sizeof( dp ) );scanf("%d",&n);for( i=1;i<n;i++ ) scanf("%d",&a[i]); // 从 1 开始方便捋清思路x=y=i=1; length_max=dp[1]=a[1]; // = 右结合性 初始化for( j=2;j<n;j++ ){// 01 判 dp[j-1]if( dp[j-1]>=0 ) dp[j]=dp[j-1]+a[j]; // 权值总和else { dp[j]=a[j]; i=j; } // 更新起始站// 02 判 dp[j]// ( largest j - i ) && ( lowest i ) just < 不取等 // ( 取等会被后值更新 不合要求 )if( length_max==dp[j] && y-x<j-i || length_max<dp[j] ){y=j; x=i; length_max=dp[j];}} // y+1 实际终点站if( length_max>=0 ) printf("The nicest part of route %d is between stops %d and %d\n",cnt++,x,y+1);else printf("Route %d has no nice parts\n",cnt++); }return 0;
}