uva 507 - Jill Rides Again

题目意思：   有一个人想要骑自行车去旅游，但是现在有s-1条路，每一条都有一个值，正值表示他喜欢然后他会骑自行车，负数表示他不喜欢他做公交。现在问这根骑自行车的最长的道路

解题思路：
1思路：DP，最大子段和的变形
2题目输出要求：1 如果max小于0，输出 “Route %d has no nice parts/n"，否则输出其它;  2如果有多个相同的max，输出序列最长的，如果最长的也有多个输出起始点最小的。
3解题过程分析：按照求最大的子段和的思路去求max，在更新max的时候注意要更新起始点位置和终点位置

代码：
[cpp] 
#include <algorithm>   
#include <iostream>  
#include <cstring> 
#include <cstdio>  
using namespace std; 
#define MAXN 20010 
 
int t , s; 
int value[MAXN]; 
long long  dp[MAXN]; 
int start , end , len; 
 
void solve(int k){ 
    long long max; 
    int tmpStart , tmpEnd , tmpLen; 
    memset(dp , 0 , sizeof(dp)); 
    start = 1 ; end = 2 ; len = 1; 
    tmpStart = 1 ; tmpEnd = 2 ; tmpLen = 1; 
    dp[1] = value[1] ; max = dp[1]; 
    for(int i = 2 ; i < s; i++){/*枚举每一个点*/ 
        if(dp[i-1] >= 0){/*如果dp[i-1]>=0*/ 
            dp[i] = dp[i-1]+value[i]; 
            tmpEnd = i+1 ;  tmpLen++ ;/*更新tmpEnd 和tmpLen*/ 
            if(max < dp[i]){/*如果max小于dp[i]，更新max和start 和end 和len*/ 
                max = dp[i] ;  
                start = tmpStart ; end = tmpEnd; 
                len = tmpLen; 
            } 
            else if(max == dp[i]){/*相等的时候也要判断当前的长度tmpLen 是否大于len*/ 
                if(tmpLen > len){ 
                   start = tmpStart ; end = tmpEnd; 
                   len = tmpLen; 
                } 
            } 
        } 
        else { /*如果dp[i-1] < 0 */ 
            dp[i] = value[i] ; tmpStart = i; 
            tmpEnd = i+1 ; tmpLen = 1;/*更新tmpEnd 和tmpLen*/ 
            if(max < dp[i]){/*如果max < dp[i],更新max 和 start和end 和len*/ 
                max = dp[i] ; len = tmpLen; 
                start = tmpStart ; end = tmpEnd; 
            } 
        } 
    } 
    printf("The nicest part of route %d is between stops %d and %d/n",k , start , end); 
} 
 
int main() { 
    //freopen("input.txt" , "r" , stdin); 
    int i , k , flag; 
    scanf("%d%*c" , &t); 
    for(k = 1 ; k <= t ; k++){ 
        scanf("%d*c" , &s) ; flag = 0;/*flag 标记是否出现正数*/ 
        for(i = 1 ; i < s; i++){ 
            scanf("%d*c" , &value[i]); 
            if(value[i] > 0) flag = 1; 
        } 
        if(flag) solve(k); 
        else printf("Route %d has no nice parts/n" , k); 
    } 
    return 0; 
}