https://www.felix021.com/blog/read.php?1587
什么是最大连续子序列和呢 ？
最大连续子序列和是所有子序列中元素和最大的一个 。
问题 ：
给定一个序列 { -2, 11, -4, 13, -5, -2 } ， 则最大连续子序列和为 20 ， 即 { 11 ， -4 ， 13 } 。
分析 ：
要怎样去解决这个问题呢 ？ 设出 两个变量 ， 一个 ans 用来存放最终的结果 ， 一个用来现在对元素进行加和 ， 每当有最大的和则更形下 ans 。
代码示例 ：
#include#include #include #include using namespace std ;#define Min(a,b) a>b?b:a#define Max(a,b) a>b?a:bint main ( ) { int a[6] = {-2, 11, -4, 13, -5, -2 } ; int ans = 0 , now = 0 ; for ( int i = 0 ; i < 6 ; i++ ) { now += a[i] ; if ( now < 0 ) now = 0 ; if ( ans < now ) ans = now ; // 每次更新 ans 的值 ， 那么 ans 中存的一定是最大的元素和 } cout << ans << endl ; return 0 ;}
题目 ： HDU 1003 http://acm.hdu.edu.cn/showproblem.php?pid=1003
HDU 1422
世界杯结束了,意大利人连本带利的收回了法国人6年前欠他们的债,捧起了大力神杯,成就了4星意大利. 世界杯虽然结束了,但是这界世界杯给我们还是留下许多值得回忆的东西.比如我们听到了黄名嘴的3分钟激情解说,我们懂得了原来可以向同一个人出示3张黄牌，我们还看到了齐达内的头不仅能顶球还能顶人………… 介于有这么多的精彩,xhd决定重温德国世界杯,当然只是去各个承办世界杯比赛的城市走走看看.但是这需要一大比钱,幸运的是xhd对世界杯的热爱之情打动了德国世界杯组委会,他们将提供xhd在中国杭州和德国任意世界杯承办城市的往返机票,并说服了这些城市在xhd到达这座城市时为他提供一笔生活费以便他在那里参观时用,当参观完时剩余的钱也将留给xhd,但当生活费不够时他们将强行结束xhd的这次德国之行,除了这个,他们还有一个条件,xhd只能根据他们所给的路线参观.比如有3座城市a,b,c,他们给定了a-b-c-a的路线,那么xhd只有3种参观顺序abc,bca,cab.由于各个城市所提供的生活费和在那里的花费都不同,这使xhd很头痛,还好我们事先知道了这笔生活费和花费.请问xhd最多能顺利参观几座城市?
Input每组输入数据分两行,第一行是一个正整数n(1<=n<=100000),表示有n座城市.接下来的一行按照给定的路线顺序的输出这n个城市的生活费和花费,w1,l1,w2,l2,……,wn,ln,其中wi,li分别表示第i个城市的生活费和花费,并且它们都是正整数.Output对应每组数据输出最多能参观的城市数.Sample Input
33 2 3 4 2 233 2 3 4 2 3Sample Output
32 题目分析 ： 由题意分析可知，它会构成一个环型的串，因此可以将串延长一倍，并且设置一个保存剩余花费的变量， 状态转移方程为 dp[i] = dp[i-1]+1 。 代码示例：
#include#include #include #include using namespace std ;#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:aint dp[200005];int w[200005] , l[200005];int main (){ int n ; int i , j; int a , b; while (~scanf("%d", &n)){ memset (dp, 0, sizeof(dp)); for (i = 1 ; i <= n; i++){ scanf("%d%d", &w[i], &l[i]); w[i+n] = w[i]; l[i+n] = l[i]; } int cost = 0; int ans = 0; for (i = 1; i <= 2*n; i++){ if (cost + w[i] >= l[i]){ dp[i] = dp[i-1]+1; cost = cost+w[i]-l[i]; } else cost = 0; if (dp[i] > ans) ans = dp[i]; } if ( ans > n) ans = n; printf ("%d\n", ans ); } return 0;}