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;
}