POJ 1952 BUY LOW, BUY LOWER DP记录数据 - c++编程基础

TOP

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

2015-07-20 17:50:33 来源: 作者: 【大中小】浏览:13次

Tags：POJ 1952 BUY LOW LOWER 记录数据

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

最麻烦的就是去重了。

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

有点绕口。

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

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

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


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：uva 12130 - Summits(BFS)	下一篇：hdu 4975 最大流及其唯一性判定（..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: