本文主要是介绍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又骑车了)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!