poj 1952 BUY LOW, BUY LOWER[最长单调子序列变形]

阳光穿透心脏的1/2处 2022-08-08 05:10 6阅读 0赞

题目：[poj 1952 BUY LOW, BUY LOWER][poj 1952 BUY LOW_ BUY LOWER]  
题意：给出一个序列，先求最长单调递减子序列，然后求在子序列最长的情况下，不同的长度都为最长的的子序列的个数。（比如3，2，1和3，2，1属于相同，只能算一个）

分析：首先用一个dp【i】表示到当前i点的最长子序列的长度  
用dp2【i】表示最长为dp【i】的子序列的个数  
然后dp【i】 = max（dp【j】）+1 （1<=j

/************************************
    Problem: 1952       User: y990041769
    Memory: 440K        Time: 94MS
    Language: G++       Result: Accepted
    Source Code*************************/
    #include <cstdio>
    #include <cstdlib>
    #include <ctime>
    #include <cstring>
    #include <algorithm>
    #include <map>
    #include <vector>
    using namespace std;
    const int N = 5500;
    int a[N];
    int dp[N],dp2[N];
    int num[N];
    int cnt;
    int Bin_search(int l,int r,int val)
    {
        while(l<=r)
        {
            int mid = (l+r)/2;
            if(num[mid]>val)
                l = mid+1;
            else
                r = mid-1;
        }
        return l;
    }
    
    int main()
    {
    //    freopen("Input.txt","r",stdin);
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=1; i<=n; i++){
                scanf("%d",&a[i]);
                dp[i] = dp2[i] = 1;
            }
            for(int i=1; i<=n; i++)
            {
                for(int j=i-1; j>0; j--)
                {
                    if(a[i]<a[j])
                    {
                        if(dp[i]<(dp[j]+1))
                        {
                            dp[i] = dp[j]+1;
                            dp2[i] = dp2[j];
                        }
                        else if(dp[i]==(dp[j]+1))
                            dp2[i]+=dp2[j];
                    }
                    else if(a[i]==a[j])
                    {
                        if(dp[i] == 1)
                            dp2[i] = 0;
                        break;
                    }
                }
            }
            int ma = 0;
            for(int i=1; i<=n; i++)
                ma = max(ma,dp[i]);
            int ans = 0;
            for(int i=1; i<=n; i++)
                if(dp[i]==ma)
                    ans += dp2[i];
            printf("%d %d\n",ma,ans);
        }
        return 0;
    }

[poj 1952 BUY LOW_ BUY LOWER]: http://poj.org/problem?id=1952