猫史档案馆

//1.2最长上升子序列

#include<iostream>

using namespace std;

int main(){

       int a[100005],b[100005],i,j,maxn=0,n;

       for(i=0;i<100005;i++)b[i]=1;

       cin>>n;

       for(i=0;i<n;i++)cin>>a[i];

       for(i=0;i<n;i++){

              for(j=0;j<=i;j++){

                     if(a[i]>a[j])b[i]=max(b[i],b[j]+1);

              }

       }

       for(i=0;i<n;i++){

              if(b[i]>maxn)maxn=b[i];

       }

       cout<<maxn;

       return 0;

}

给出一个数列{a1,a2,...,an},要求你选出尽量多的元素，使这些元素按其相对位置单调递增。对于给定的序列，求出最长上升子序列的长度。

这就是典型的动态规划题最长上升子序列。

哦么来看一下这一题，首先，数组一个，用来存储数列。设一个数列，1 3 2 4 3 5 4 6 5 7，

分别对应a[i]的下标的值为0123456789.首先两个变量，i和j。i到0，序列为1；b[0]就为一。这时下标到了2，其中，3>1，因此b2为2……以此类推。

状态转移方程: if(a[i]>a[j])b[i]=max(b[i],b[j]+1);

那么这就是我们动态规划的一个基本的解题流程。

动态规划要满足以下条件：

最优子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

子问题独立：一个子问题的状态不会影响到另一个子问题。

子问题重叠：母问题与子问题实质上是同一个问题。

最后我们以一个故事结尾：

有一个国家，所有的国民都非常老实憨厚，某天他们在自己的国家发现了十座金矿，并且这十座金矿在地图上排成一条直线，国王知道这个消息后非常高兴，他希望能够把这些金子都挖出来造福国民，首先他把这些金矿按照在地图上的位置从西至东进行编号，依次为0、1、2、3、4、5、6、7、8、9，然后他命令他的手下去对每一座金矿进行勘测，以便知道挖取每一座金矿需要多少人力以及每座金矿能够挖出多少金子，然后动员国民都来挖金子。但是国王只有10000个人。国王首先来到了第9个金矿的所在地，他的臣子告诉他，如果要挖取第9个金矿的话就需要1500个人，并且第9个金矿可以挖出8888个金子。听到这里国王哈哈大笑起来，因为原先以为要知道十个金矿在仅有10000个人的情况下最多能挖出多少金子是一件很难思考的问题，但是，就在刚才听完他的臣子所说的那句话时，国王已经知道总共最多能挖出多少金子了，国王是如何在不了解其它金矿的情况下知道最多能挖出多少金子的呢？因此他的臣子们就问他了：“最聪明的国王陛下，我们都没有告诉您其它金矿的情况，您是如何知道最终答案的呢？”得意的国王笑了笑，然后把他最得意的“左、右手”叫到跟前，说到：“我并不需要考虑最终要挖哪些金矿才能得到最多的金子，我只需要考虑我面前的这座金矿就可以了，对于我面前的这座金矿不外乎仅有两种选择，要么挖，要么不挖，对吧？”“当然，当然”大臣们回答倒。国王继续说道：“如果我挖取第9座金矿的话那么我现在就能获得8888个金子，而我将用去1500个人，那么我还剩下8500个人。我亲爱的左部下，如果你告诉我当我把所有剩下的8500个人和所有剩下的其它金矿都交给你去开采你最多能给我挖出多少金子的话，那么我不就知道了在第9个金矿一定开采的情况下所能得到的最大金币数吗？”国王的左部下听后回答道：“国王陛下，您的意思是如果我能用8500个人在其它金矿最多开采出x个金币的话，那您一共就能够获得x + 8888个金子，对吗？”“是啊……如果第9座金矿一定开采的话……”大臣们点头说到。国王笑着对着他的右部下说到：“亲爱的右部下，也许我并不打算开采这第9座金矿，那么我依然拥有10000个人，如果我把这10000个人和剩下的金矿都给你的话，你最多能给我挖出多少个金子呢？”国王的右部下聪明地说道：“尊敬的国王陛下，我明白您的意思了，如果我回答最多能购开采出y个金币的话，那您就可以在y和x+8888之间选择一个较大者，而这个较大者就是最终我们能获得的最大金币数，您看这样理解对吗？”国王笑得更灿烂了，问他的左部下：“亲爱的左部下，我给你8500个人和其余金矿的话你能告诉我最多能挖出多少金子吗？”“请您放心，这个问题难不倒我”。左部下向国王打包票说到。国王高兴地继续问他的右部下：“那右部下你呢，如果我给你10000个人和其余金矿的话你能告诉我最多能挖出多少金子吗？”“当然能了！交给我吧！”右部下同左部下一样自信地回答道。“那就拜托给你们两位了，现在我要回到我那舒适的王宫里去享受了，我期待着你们的答复。”国王说完就开始动身回去等消息了，他是多么地相信他的两个大臣能够给他一个准确的答复，因为国王其实知道他的两位大臣要比他聪明得多。故事发展到这里，你是否在想国王的这两个大臣又是如何找到让国王满意的答案的呢？国王走后，国王的左、右部下来到了第8座金矿，早已在那里等待他们的金矿勘测兵向两位大臣报道：“聪明的两位大臣，您们好，第8座金矿需要1000个人才能开采，可以获得7000个金子”。因为国王仅给他的左部下8500个人，所以国王的左部下叫来了两个人，对着其中一个人问到：“如果我给你7500个人和除了第8、第9的其它所有金矿的话，你能告诉我你最多能挖：“如果我给你7500个人和除了第8、第9的其它所有金矿的话，你能告诉我你最多能挖出多少金子吗？”国王的左部下继续问另一个人：“如果我给你8500个人和除了第8、第9的其它所有金矿的话，你能告诉我你最多能挖出多少金子吗？”国王的左部下想着：“如果他们俩都能回答我的问题的话，那国王交给我的问题不就解决了吗？哈哈哈！”因为国王给了他的右部下10000个人，所以国王的右部下同样也叫来了两个人，对着其中一个人问：“如果我给你9000个人和除了第8、第9的其它所有金矿的话，你能告诉我你最多能挖出多少金子吗？”然后国王的右部下继续问他叫来的另一个人：“如果我给你10000个人和除了第8、第9的其它所有金矿的话，你能告诉我你最多能挖出多少金子吗？”当然，这四个被叫来的人同样自信地回答没有问题，因为他们同样地从这两个大臣身上学到了相同的一点，而两位自认为自己一样很聪明的大臣得意地笑着回到了他们的府邸，等着别人回答他们提出来的问题，现在你知道了这两个大臣是如何解决国王交待给他们的问题了吗？那么你认为被大臣叫去的那四个人又是怎么完成大臣交给他们的问题的呢？答案是他们又找到了八个人！这个问题已经在全国传开了，更多人找到了更多人来解决这个问题，而有些人却不需要去另外找两个人帮他，很明显，当被问到给你z个人和仅有第0座金矿时最多能挖出多少金子时，就不需要别人的帮助，如果z大于等于挖取第0座金矿所需要的人数的话，那么挖出来的最多金子数就是第0座金矿能够挖出来的金子数，如果这z个人不够开采第0座金矿，那么能挖出来的最多金子数就是0，因为这唯一的金矿不够人力去开采。让我们为这些不需要别人的帮助就可以准确地得出答案的人们鼓掌吧，这就是传说中的底层劳动人民！

爵士OIer

//1.2最长上升子序列

#include<iostream>

using namespace std;

int main(){

       int a[100005],b[100005],i,j,maxn=0,n;

       for(i=0;i<100005;i++)b[i]=1;

       cin>>n;

       for(i=0;i<n;i++)cin>>a[i];

       for(i=0;i<n;i++){

              for(j=0;j<=i;j++){

                     if(a[i]>a[j])b[i]=max(b[i],b[j]+1);

              }

       }

       for(i=0;i<n;i++){

              if(b[i]>maxn)maxn=b[i];

       }

       cout<<maxn;

       return 0;

}