首页 > 代码库 > 【最长下降子序列的长度和个数】 poj 1952
【最长下降子序列的长度和个数】 poj 1952
转自http://blog.csdn.net/zhang360896270/article/details/6701589
这题要求最长下降子序列的长度和个数，我们可以增加数组maxlen[size]（记录当前第1个点到第i个点之间的最长下降序列长度）和maxnum[size]（记录1~i之间的最长下降序列个数 ），首先对于最长下降序列属于DP基础题，只要对每一个a[i]求出符合要求（a[i] < a[j]）的max( maxlen[j] + 1)即可，主要难点在第二步求下降序列总数
在序列中，如果maxlen[j]+1 == maxlen[i]则说明a[i]和a[j]在同一个下降数列中，那么我们只要将每一种符合要求的状态maxnum[j]转移到maxnum[i]中就可以了，有几个细节需要注意，题目要求序列是严格递减的，那么对于两个相同的数我们只能记录一个合法解，那么程序必须只记录两个相同数之间的状态，在这里用倒推可以简化编程，只要找到一个等于的就直接跳出循环，还要注意，如果从当前的a[i]一直找到相等的a[j]在这之间都没有可行状态的话，当maxnum[i]默认值为1要修改为0（避免错误计算），为0的当然无需处理。
#include <iostream>#include <string.h>#include <cstdio>using namespace std;const int size = 5100;int maxlen[size];//记录当前第1个点到第i个点之间的最长下降序列长度int maxnum[size];//记录1~i之间的最长下降序列个数int main(){ //freopen("in.txt","r",stdin); int a[size]; int n; while (scanf("%d", &n) != EOF){ for (int i = 1; i <= n; i ++){ scanf("%d", &a[i]); maxnum[i] = 0; maxlen[i] = 1; } for (int i = 1 ; i <= n; i ++){ for (int j = 1; j < i; j ++){ if (a[i] < a[j]){ maxlen[i] = max(maxlen[i], maxlen[j]+1); } } } for (int i = 1; i <= n; i ++) if (maxlen[i] == 1)maxnum[i] = 1; for (int i = 1; i <= n; i ++){ for (int j = i-1; j > 0; j --){ if (a[j] > a[i]){ if (maxlen[j]+1 == maxlen[i]){ maxnum[i] += maxnum[j]; } } if (a[j] == a[i]){ if (maxlen[i] == 1)maxnum[i] = 0;//如果搜索到一个相同的数后仍没有找到符合要求的序列，则为了避免重复赋值为0 break; } } } int maxx = -1; for (int i = 1; i <= n; i ++){ if (maxlen[i] > maxx) maxx = maxlen[i]; } int ans = 0; for (int i = 1; i <= n; i ++){ if (maxlen[i] == maxx) ans += maxnum[i] ; } printf("%d %d\n", maxx, ans); } return 0;}
【最长下降子序列的长度和个数】 poj 1952
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。