首页 > 代码库 > POJ 1952 BUY LOW, BUY LOWER DP记录数据

POJ 1952 BUY LOW, BUY LOWER DP记录数据

2024-07-19 04:16:39   217人阅读

最长递减子序列，加记录有多少个最长递减子序列，然后需要去重。

最麻烦的就是去重了。

基本的思路就是：全面出现重复的值，然后还是相同长度的子序列，这里的DP记录的子序列是以当前值为结尾的时候，并且一定选择这个值的最长递减子序列， 那么就需要减去前面已经出现过了的子序列。

有点绕口。

举例就是9 8 9 8 2 和 10 5 12 5 3；这些例子去重。

本类型的题目如果不用记录数据是可以使用O(nlgn)的算法的，不过暂时不知道如何记录数据。故此这里只使用DP了。


[cpp] view plaincopyprint?
  1. #include <stdio.h>  
  2. #include <vector>  
  3. #include <string.h>  
  4. #include <algorithm>  
  5. #include <iostream>  
  6. #include <string>  
  7. #include <limits.h>  
  8. #include <stack>  
  9. #include <queue>  
  10. #include <set>  
  11. #include <map>  
  12. using namespace std;  
  13. const int MAX_N = 5001;  
  14. int arr[MAX_N], N, tbl[MAX_N], C[MAX_N];  
  15.   
  16. void getLongest(int &len, int &n)  
  17. {  
  18.     memset(tbl, 0, sizeof(int) * (N+1));  
  19.     memset(C, 0, sizeof(int) * (N+1));  
  20.     tbl[0] = 1; C[0] = 1;  
  21.     for (int i = 1; i < N; i++)  
  22.     {  
  23.         tbl[i] = 1;  
  24.         for (int j = 0; j < i; j++)  
  25.         {  
  26.             if (tbl[j] == -1) continue;  
  27.             if (arr[j] > arr[i] && tbl[i] < tbl[j]+1)  
  28.             {  
  29.                 tbl[i] = tbl[j]+1;  
  30.             }  
  31.         }  
  32.         for (int j = 0; j < i; j++)  
  33.         {  
  34.             if (arr[j] > arr[i] && tbl[i] == tbl[j]+1)  
  35.             {  
  36.                 C[i] += C[j];  
  37.             }  
  38.         }  
  39.         if (C[i] == 0) C[i] = 1;//递增的时候  
  40.         /*可以不用下面这段代码 
  41.         for (int j = 0; j < i; j++) 
  42.         { 
  43.             if (arr[i] == arr[j] && tbl[i] == tbl[j] && C[i] == C[j]) 
  44.             { 
  45.                 tbl[i] = -1; 
  46.                 break; 
  47.             }//去掉相同的数据 9 8 9 8 
  48.         } 
  49.         if (tbl[i] == -1) continue;*/  
  50.   
  51.         for (int j = 0; j < i; j++)  
  52.         {  
  53.             if (arr[j] == arr[i] && tbl[j] == tbl[i]) C[i] -= C[j];  
  54.         }//特例：6 5 7 5 3 需要去掉前后5重复的地方  
  55.     }  
  56.     len = INT_MIN;  
  57.     for (int i = 0; i < N; i++)  
  58.     {  
  59.         len = max(len, tbl[i]);  
  60.     }  
  61.     n = 0;  
  62.     for (int i = 0; i < N; i++)  
  63.     {  
  64.         if (tbl[i] == len) n += C[i];  
  65.     }  
  66. }  
  67.   
  68. int main()  
  69. {  
  70.     while (scanf("%d", &N) != EOF)  
  71.     {  
  72.         for (int i = 0; i < N; i++)  
  73.         {  
  74.             scanf("%d", arr + i);  
  75.         }  
  76.         int len, n;  
  77.         getLongest(len, n);  
  78.         printf("%d %d\n", len, n);  
  79.     }  
  80.     return 0;  
  81. } 

POJ 1952 BUY LOW, BUY LOWER DP记录数据


联系
我们