UVA - 507 - Jill Rides Again (dp最大子段和)_如果jill在城市i开始骑自行车,在城市j(j>i)又开始坐公共汽车,-程序员宅基地

技术标签: uva  Jill Rides Again  动态规划  507  

题目大意:
Jill喜欢骑自行车,但是自从他的城市有了公交系统后,他就比较少骑车了,于是他买了一个折叠自行车,这样他就可以把自行车带到公交车上,当他下车后,他就可以继续骑车。
现在b条道路,每条道路有n个公交站点,两个站点间都有一个喜欢值,现在问你能否求出,哪两个站点间的喜欢值最大,如果有多个最大值,输出其中距离最远的站点。


解析:
题如果用普通枚举起点和终点的O(n^3)肯定超时,所以要用dp来做。

最大字段和dp公式的推导:

若记dp[j] = max(a[i]+a[i+1]+..+a[j]),
其中1 <= i <= j,并且1<=j<=n
则所求的最大子段和为max(dp[j]),1 <= j <= n。
由dp[j]的定义可易知,
当dp[j-1]>0时
dp[j] = dp[j-1]+a[j],
否则
dp[j] = a[j]
故dp[j]的动态规划递归式为:

dp[j] = max(dp[j-1]+a[j],a[j]),1<=j<=n。

#include <stdio.h>
#include <string.h>
const int INF = 0x3f3f3f;
const int N = 20010;
int arr[N],dp[N];
int main() {
	int t,n,cas = 1;
	scanf("%d",&t);
	while(t--) {
		memset(dp,0,sizeof(dp));
		scanf("%d",&n);
		arr[0] = 0;
		for(int i = 1; i < n; i++) {
			scanf("%d",&arr[i]);
		}
		int max;
		int left,right,start;
		left = right = start = 1;
		dp[1] = max = arr[1];
		for(int i = 2; i < n; i++) {
			if(dp[i-1] >= 0) {
				dp[i] = dp[i-1] + arr[i];
			}else {
				dp[i] = arr[i];
				start = i;
			}
			if(max < dp[i] || max == dp[i] && i - start > right - left) {
				left = start;
				right = i;
				max = dp[i];
			}
		}
		if(max >= 0) {
			printf("The nicest part of route %d is between stops %d and %d\n",cas++,left,right+1);
		}else {
			printf("Route %d has no nice parts\n",cas++);
		}
	}
	return 0;
}

附上一组样例:

input

10

6
1
0
0
0
1


6
1
0
0
1
-1

6
0
0
0
0
0

10
4
-5
4
-3
4
4
-4
4
-5

10
4
-5
4
-3
4
4
-4
4
5

6
-1
1
-1
1
-1

6
1
-1
1
-1
1

11
1
-1
1
-1
1
-1
1
-1
1
-1

12
1
-1
1
-1
1
-1
1
-1
1
-1
1

7
1
-1
1
-100
1
-1
1

ac output

The nicest part of route 1 is between stops 1 and 6
The nicest part of route 2 is between stops 1 and 5
The nicest part of route 3 is between stops 1 and 6
The nicest part of route 4 is between stops 3 and 9
The nicest part of route 5 is between stops 3 and 10
The nicest part of route 6 is between stops 2 and 5
The nicest part of route 7 is between stops 1 and 6
The nicest part of route 8 is between stops 1 and 10
The nicest part of route 9 is between stops 1 and 12
The nicest part of route 10 is between stops 1 and 4


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/HelloWorld10086/article/details/40214471

智能推荐

java.lang.ClassNotFoundException: org.apache.commons.beanutils.BeanUtils-程序员宅基地

文章浏览阅读442次。今天有伙伴求助我这个bug,怎么解决,看提示,很明显,要么就是没有导入jar包,要么就是导入jar包之后,没有添加到库,即Add as library 没有选添加完jar包后,这一步一定不要忘选,

ssh远程No route to host问题解决_ssh no route to host-程序员宅基地

文章浏览阅读5.2w次,点赞13次,收藏71次。ssh远程No route to host问题解决问题描述服务器ssh 端口设为10022主机A192.168.237.1/24 远程登录虚拟主机B192.168.237.138报错:ssh: connect to host 192.168.237.136 port 10022: No route to host解决思路ssh端口设置是否正确网络是否可达防火墙策略是否合理1..._ssh no route to host

跟着实训学习HTML CSS的第二天-程序员宅基地

文章浏览阅读72次。在练习五彩导航条的时候,许多同学都卡住了,最后经过分享,大家掌握了许多的方法来解决这个问题,还是很有帮助的。下面就是代码的实现部分:<!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="wi

dfs 遍历二叉树_dfs遍历思想实际上是二叉树-程序员宅基地

文章浏览阅读830次。dfs 遍历二叉树为了更好的理解dfs手写了dfs 遍历二叉树的两种方式方法:一种是采用常用的递归执行另一种是采用循环执行(使用栈来代替递归)二叉树定义class Node { //get set方法省略 private Node leftChild; private Node rightChild; private int data; public Node(int d..._dfs遍历思想实际上是二叉树

手握Synchronized原理搞懂并发编程,阿里面试官:快到碗里来_python synchronized原理-程序员宅基地

文章浏览阅读478次。Synchronized原理简介synchronized想必大家都不陌生,用来解决线程安全问题的利器。同时也是Java高级程序员面试比较常见的面试题。下面会带大家彻底了解synchronized的实现。内容导航什么时候需要用Synchronized synchronized的使用 synchronized的实现原理分析什么时候需要用Synchronized想必大家对synchronized都不陌生,主要作用是在多个线程操作共享数据的时候,保证对共享数据访问的线程安全性。比如在下_python synchronized原理

同为容器,IoC和Docker有啥不同?_部署容器和ioc容器的区别-程序员宅基地

文章浏览阅读1.1w次,点赞87次,收藏121次。Spring中有容器技术,Docker中也有,容器技术中,能学到哪些思想呢?_部署容器和ioc容器的区别

随便推点

2021春招BAT面试真题详解,java语言允许运算符重载-程序员宅基地

文章浏览阅读90次。前言俗话说“生于忧患,死于安乐”,其实大部分中年危机,就是在安乐中产生的。有的人或许会反驳,“照你这么说,我还必须奋斗了,不奋斗就要死,难道选择安逸的生活就不对吗?我就没有选择自己生活方式的权利吗?”说这句话的人其实有一些误解,误解就在于,安逸的生活并不等于不需要奋斗,这要看你的家底。某聪如果说要选择安逸的生活,他可以很安逸,因为他有了安逸的资本,而大部分的你,并没有这个资本,你如果过早的选择了安逸的生活,那么结局往往会很悲惨,而你能做的,最多也就是让你的后代有选择安逸的资本。而你,并没有这个选择_java语言允许运算符

孪生神经网络(Siamese neural network)-程序员宅基地

文章浏览阅读1.3k次,点赞2次,收藏4次。Cosine是一个选择,exp function也是一种选择,欧式距离什么的都可以,训练的目标是让两个相似的输入距离尽可能的小,两个不同类别的输入距离尽可能的大。从图中可以看到,他又两个输入,分别是x1和x2,左右两个的网络结构是一样的,并且他们共享权重,最后得到两个输出,分别是Gw(x1)和Gw(x2),这个网络的很好理解,当输入是同一张图片的时候,我们希望他们之间的欧式距离很小,当不是一张图片时,我们的欧式距离很大。(2) 当我们的输入是不同的图片的时候,他们之间的距离越大,损失越小。_孪生神经网络

0-1背包问题(python实现)_python实现0-1背包问题-程序员宅基地

文章浏览阅读619次。定义一个二维数组 dp,其中dp[i][j]表示 将下标为 0-i之间的物品放入容量为j的背包的最大价值。_python实现0-1背包问题

牙齿开奶_怎么用牙开牛奶-程序员宅基地

文章浏览阅读102次。对学校的饭堂越来越不满意了,以前一直缺汤匙,今天更缺吸管了。今天买了一袋奶,找不到吸管,当时问服务员借剪刀她说没有,问她怎样开,她说真是读书读傻了,用牙齿嘛。我无语。。。想不到从小没有极尽牙齿之能的我,今天竟然第一次动用牙齿来代替剪刀了。不过想到其他同学牙齿的功效远不止剪刀的作用,我也只有尝试尝试这剪刀的威力了。不知道爱护牙齿是否必须通过这样锻炼出来的呢?2008-3-8..._怎么用牙开牛奶

go 判断字符是否为汉字或ascii码_go 字符串 asci码判断-程序员宅基地

文章浏览阅读9.2k次。判断是否为汉字func isHan(r rune) bool { return unicode.Is(unicode.Han, r)}判断是否为ascii码. 对应c的 int isascii(int c);func isAscii(r rune) bool { return unicode.Is(unicode.ASCII_Hex_Digit, r)..._go 字符串 asci码判断

Android开发小生(四)-程序员宅基地

文章浏览阅读346次。深入探讨Activity

推荐文章

热门文章

相关标签