uva507 - Jill Rides Again(JIll又骑车了)

本文主要是介绍uva507 - Jill Rides Again(JIll又骑车了)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路不难，就是暴力，

两层暴力。不过要剪枝，

考虑那次循环是无用的，则跳过那样的耗时、

假如1~m目前求得的最大值是M。

那么如果a[1]>0的话，就没有必要让i=2再来一次循环了，因为a[1]>0,所以2~m最大值会比M少a[1].，所以把这样的无用功剪去就好了

代码如下：

#include <cstdio>
#define M 20010
int n, a[M];
int main ()
{int cas, t = 0, n, sum, maxi, maxj, max, m;scanf("%d",&cas);while(t++<cas){scanf("%d",&n);for(int i = 1; i < n; i++) scanf("%d",&a[i]);a[0] = -1; sum = -1; maxi = maxj = max = m = 0;for(int i = 1; i < n; i++){m+=a[i-1];//剪枝条件判断if(m>=0) continue;sum = 0;for(int j = i; j < n; j++){sum+=a[j];//printf("%d  %d = %d\n",i,j,sum);if(sum>max) {max = sum; maxi = i; maxj = j;}if(sum==max&&maxj-maxi<j-i) {max = sum; maxi = i; maxj = j;}}m = 0;}if(max<=0) printf("Route %d has no nice parts\n",t);else printf("The nicest part of route %d is between stops %d and %d\n",t,maxi, maxj+1);}return 0;
}

这篇关于uva507 - Jill Rides Again(JIll又骑车了)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---