Poj动态规划

介绍一：LIS（Longest Increasing Subsequence）最长上升（不下降）子序列，有两种算法复杂度为O(n*logn)和O(n^2)。

在上述算法中，若使用朴素的顺序查找在D1..Dlen查找，由于共有O(n)个元素需要计算，每次计算时的复杂度是O(n)，则整个算法的时间复杂度为O(n^2)，与原来算法相比没有任何进步。

但是由于D的特点(2)，在D中查找时，可以使用二分查找高效地完成，则整个算法时间复杂度下降为O(nlogn)，有了非常显著的提高。

需要注意的是，D 在算法结束后记录的并不是一个符合题意的最长上升子序列！算法还可以扩展到整个最长子序列系列问题。

有两种算法复杂度为O(n*logn)和O(n^2)O(n^2)算法分析如下（a[1]...a[n] 存的都是输入的数）1、对于a[n]来说，由于它是最后一个数，所以当从a[n]开始查找时，只存在长度为1的不下降子序列；2、若从a[n-1]开始查找，则存在下面的两种可能性：（1）若a[n-1] < a[n] 则存在长度为2的不下降子序列a[n-1],a[n].（2）若a[n-1] > a[n] 则存在长度为1的不下降子序列a[n-1]或者a[n]。

3、一般若从a[t]开始，此时最长不下降子序列应该是按下列方法求出的：在a[t+1],a[t+2],...a[n]中，找出一个比a[t]大的且最长的不下降子序列，作为它的后继。

4、为算法上的需要，定义一个数组：d:array [1..n,1..3] of integer;d[t,1]表示a[t]d[t,2]表示从i位置到达n的最长不下降子序列的长度d[t,3]表示从i位置开始最长不下降子序列的下一个位置最长不下降子序列的O(n*logn)算法先回顾经典的O(n^2)的动态规划算法，设A[t]表示序列中的第t个数，F[t]表示从1到t 这一段中以t结尾的最长上升子序列的长度，初始时设F[t] = 0(t = 1, 2, ..., len(A))。

POJ2479Maximumsum解题报告Maximum sumTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 40596Accepted: 12663DescriptionGiven a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:Your task is to calculate d(A).InputThe input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input.Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.OutputPrint exactly one line for each test case. The line should contain the integer d(A).Sample Input1101 -12 23 -34 -45 -5Sample Output13HintIn the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.Huge input,scanf is recommended.Source,Author:Mathematica@ZSU题⽬⼤意：给定⼀个整数数字序列s，要求使两段不相交的⼦序列s1,s2的和最⼤题解：动态规划ls[i]表⽰以第i个元素结尾序列的最⼤值rs[i]表⽰以第i个元素开始序列的最⼤值rst[i]表⽰取i个元素能够达到的最⼤值所以有ls[i]=max(ls[i-1]+a[i], a[i]), rs[i]=max(rs[i+1]+a[i], a[i])rst[i]=max(rst(i+1), rs[i])所以最后的答案是s=max(s, ls[i]+rst(i+1))#include <stdio.h>#include <string.h>#include <cstdio>#include <iostream>using namespace std;const int maxn = 1e6+7, inf = -1e6+7;int a[maxn], ls[maxn], rs[maxn], s, rst[maxn]; int main(){int t, n;scanf("%d", &t);while (t--){s = 0;memset(ls, 0, sizeof(ls));memset(rs, 0, sizeof(rs));memset(rst, 0, sizeof(rst));scanf("%d", &n);for (int i=0; i<n; i++)scanf("%d", &a[i]);ls[0] = a[0];for (int i=1; i<n; i++) {ls[i] = max(ls[i-1]+a[i], a[i]);}rst[n-1] = rs[n-1] = a[n-1];for (int i=n-2; i>=0; i--){rs[i] = max(rs[i+1]+a[i], a[i]);rst[i] = max(rst[i+1], rs[i]);}s = inf;for (int i=0; i<n-1; i++) {s = max(s, ls[i]+rst[i+1]);}printf("%d\n", s);}return 0;}。

ACM/ICPC新手入门指南前言：这篇指南不对ACM/ICPC国际大学生程序设计竞赛进行介绍，计算机学子如果不了解的可以在百度上进行搜索查询，这里介绍的只是一个计算机学生想要在ACM/ICPC里进行发展的初学者。

内容比较简单通俗，完全是给新接触的人看的，已经接触过的请飘过，该干嘛的干嘛去。

语言关:要进行程序设计，也就必然要熟悉编程语言，只要掌握了一门语言，就可以进行ACM训练了。

一般通用语言如C、C++、JAVA都可以，这三种语言都有自己的优势和缺点，C在效率方面比较好；但C++封装了输入输出流，方便了我们的操作也减少出错的可能性，而且C++提供了非常强大的标准模版库（STL），使得很多在C上实现起来比较麻烦的代码，在C++上却非常方便；JAVA在大型工程和安全方面都有比较独特的优势，但在ACM里面却不是一种优秀的语言，因为JAVA的执行效率要比C、C++慢很多，如果题目限时比较紧的话，就不适合用JAVA，当然JAVA为我们提供了很方便的高精度运算（大整数运算），所以个人认为，刚学完C的可以用纯C来写训练，在训练过程中可以学学C++，有时间的把STL也好好学学，这样可以减少很多不必要的劳动。

初次接触ACM训练的同学经常会遇到问题，就是输入和输出问题，所以如果对语言的输入输出问题不是很熟悉的话，要抽几天时间重点看看,特别有些初学者在输出时总会输出冗余信息，可能认为有交互性吧，但这是ACM不允许的，它不需要任何交互性。

不严格按照题目要求进行输入输出的程序是无法通过系统测试的。

熟悉在线评测系统在线评测系统，英文叫Online Judge，（简称OJ）里面提供了很多题目给我们平时训练之用。

这里以浙江大学的在线评测系统为例，网址是 先在上面进行注册，注册完后就可以进行题目的训练了，点击主页上的“Problems”，就可以看到里面的题库，可以选任何一个题来做，里面的题目不是由易到难进行排列，而初学者要选择比较简单的题目来做。

ACM训练计划建议（转）前⾔：⽼师要我们整理⼀份训练计划给下⼀届的学弟学妹们，整理出来了，费了不少笔墨，就也将它放到博客园上供⼤家参考。

菜鸟之作，⼤⽜勿喷，如有不当或补充之处，欢迎指出。

本建议书分为三个阶段，⼤⼀、⼤⼆、⼤三。

⼤四暂没整理，⼀⽅⾯是⼤四要⾯临考验和找⼯作的问题，坚持继续acm的很少，另⼀⽅⾯，本⼈还没⼤四……下⾯以个⼈经验分析⼀下这三个阶段建议学习的内容和具体的训练计划。

正⽂：⼤⼀（第⼀阶段）： ⼤⼀是时间最充裕的⼀段时间，也是可塑性最⾼的⼀个阶段。

⼤⼀你有很多⾃由时间可以⾃⼰分配，建议这段时间先打好c/c++基础，或者是任何⼀门语⾔的基础，尽量做到“半精通”。

因为像c++这种语⾔，⼏年内达到精通都是不可能的。

⽽我这⾥所说的“半精通”，实际上是将课本完全搞透的基础上，再在课外拓展⼀些内容，加深对语⾔本⾝的理解。

为什么我这⾥强调语⾔的重要性呢？⼀⽅⾯是为了以后搞acm的需要，语⾔通畅了，可以保证你实现⼤部分算法没有障碍，⽽⽐赛时，时间是很重要的。

另⼀⽅⾯，也是你⾝为学计算机的学⽣的⼀个必须要学习的能⼒，语⾔就是你⼿中的剑，以后能披荆斩棘⾛多远，剑有多锋利占很⼤因素。

另⼀⽅⾯，建议打好数学的基础。

学长⾝为过来⼈，深受数学烂的苦。

acm越到后期的时候，其实⽤到的数学知识就越多。

像有些题⽬，⾚裸裸的就是求积分，还有⼀些题⽬，将求期望嵌⼊到了DP的题⽬⾥…… 其实这些还好说，都是显式的题⽬，还有⼀种隐式的东西，对acm帮助最⼤，那就是数学思维。

有数学思维和没有数学思维的区别，就是⼀道题有N种思路和N*N种思路的区别。

这越到后期越明显，思路很重要，⽐赛时⾯对⼀道题团队⾥⾸先要有多种思路可供分析，然后⼤家讨论哪种思路是最可⾏的，确定之后就是最擅长这个思路的⼈实现算法。

如果分析⼀道题⽬的时候，产⽣的思路很少，那么⽆疑会降低这道题的AC命中率。

啰嗦了这么多，其实我就想给⼤⼀的新⽣们强调两点，语⾔和数学。

ACM竞赛简介：ACM国际大学生程序设计竞赛是由国际计算机界历史悠久、颇具权威性的组织ACM学会（美国计算机协会）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。

(网上有更详细的介绍，这里只做个简介)ACM竞赛特点：竞赛中一般有10道题，比赛时间为5个小时，每支参赛队伍由3名选手组成，可以携带诸如书、手册、程序清单等参考资料，对每一道题编完代码后，将代码提交裁判，每一次提交会被判为正确或者错误，判决结果会及时通知参赛队伍。

在规定时间内提交并通过题目数越多排名越靠前。

（时间5小时，题目8~12题，同题目数按所用时间多少排名）ACM题目限制：时间限制（即程序运行所用的时间）空间限制（即程序运行时所开内存的多少）ACM基本要求⏹英语⏹分析理解能力⏹算法⏹编码⏹合作ACM竞赛意义学习编程，并不是为了参加竞赛，ACM竞赛对于我们的意义更多的还是专业能力的提高。

在备战过程中，无论是对自己的编程能力，还是团队合作解决问题的能力，都是一种很好的锻炼机会。

一般而言，每个在做ACM竞赛的学生，他们的编程能力会比较出色。

与数学建模相比，由于ACM竞赛针对的是我们学计算机的同学，所以没有数学建模的比赛规模，但是依旧是国际上最有影响力的大学生竞赛之一。

ACM竞赛入门现在有很多大学有专门为ACM竞赛开设自己的测评网站，上面有很多贴近竞赛的题目。

比如说北大poj，浙大zoj等等。

所以选择一个自己专门练习的网站，我们都用北大的poj，然后开始自己在上面做题，和同学交流经验。

等到回到本部，要是有了一定的实力和基础，张震老师就会对我们进行选拔和组队，最后参加省赛和亚洲的区域赛。

⏹在poj上做20左右道简单的题目，熟悉ACM题目的基本特点。

（这里列出几道相对较简单的题目的题号：1000，1003，1004，1046，1207，1226，1504，1552）⏹熟悉了poj之后，按照poj的题目分类，买一本或借一本算法的书（暨大ACM校队的基本都用机械工程出版社的《算法导论》）开始学习，然后做算法的专题，一般每个专题做10~30道。