首页 > 代码库 > POJ 1952 BUY LOW, BUY LOWER DP记录数据
POJ 1952 BUY LOW, BUY LOWER DP记录数据
最长递减子序列,加记录有多少个最长递减子序列,然后需要去重。
最麻烦的就是去重了。
基本的思路就是:全面出现重复的值,然后还是相同长度的子序列,这里的DP记录的子序列是以当前值为结尾的时候,并且一定选择这个值的最长递减子序列, 那么就需要减去前面已经出现过了的子序列。
有点绕口。
举例就是9 8 9 8 2 和 10 5 12 5 3;这些例子去重。
本类型的题目如果不用记录数据是可以使用O(nlgn)的算法的,不过暂时不知道如何记录数据。故此这里只使用DP了。
#include <stdio.h> #include <vector> #include <string.h> #include <algorithm> #include <iostream> #include <string> #include <limits.h> #include <stack> #include <queue> #include <set> #include <map> using namespace std; const int MAX_N = 5001; int arr[MAX_N], N, tbl[MAX_N], C[MAX_N]; void getLongest(int &len, int &n) { memset(tbl, 0, sizeof(int) * (N+1)); memset(C, 0, sizeof(int) * (N+1)); tbl[0] = 1; C[0] = 1; for (int i = 1; i < N; i++) { tbl[i] = 1; for (int j = 0; j < i; j++) { if (tbl[j] == -1) continue; if (arr[j] > arr[i] && tbl[i] < tbl[j]+1) { tbl[i] = tbl[j]+1; } } for (int j = 0; j < i; j++) { if (arr[j] > arr[i] && tbl[i] == tbl[j]+1) { C[i] += C[j]; } } if (C[i] == 0) C[i] = 1;//递增的时候 /*可以不用下面这段代码 for (int j = 0; j < i; j++) { if (arr[i] == arr[j] && tbl[i] == tbl[j] && C[i] == C[j]) { tbl[i] = -1; break; }//去掉相同的数据 9 8 9 8 } if (tbl[i] == -1) continue;*/ for (int j = 0; j < i; j++) { if (arr[j] == arr[i] && tbl[j] == tbl[i]) C[i] -= C[j]; }//特例:6 5 7 5 3 需要去掉前后5重复的地方 } len = INT_MIN; for (int i = 0; i < N; i++) { len = max(len, tbl[i]); } n = 0; for (int i = 0; i < N; i++) { if (tbl[i] == len) n += C[i]; } } int main() { while (scanf("%d", &N) != EOF) { for (int i = 0; i < N; i++) { scanf("%d", arr + i); } int len, n; getLongest(len, n); printf("%d %d\n", len, n); } return 0; }
POJ 1952 BUY LOW, BUY LOWER DP记录数据
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。