https://vjudge.net/contest/161167#problem/F——dp

骑猪看日落 2022-06-14 05:15 148阅读 0赞

Think:  
1求非严格单调递增子序列和非严格单调递减子序列  
2反思：  
1>lower\_bound()—-Wrong Answer  
upper\_bound()—-Accepted

[建议参考博客][Link 1]

以下为Wrong Answer代码——lower\_bound()可行数据覆盖？

#include <cstdio>
    #include <algorithm>
    
    using namespace std;
    
    int n, a[100004], b[100004];
    
    int dp1();
    int dp2();
    
    int main(){
        int T, i;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            for(i = 1; i <= n; i++)
                scanf("%d", &a[i]);
            int x1 = dp1();
            int x2 = dp2();
            if(x1 == n-1 || x1 == n || x2 == n-1 || x2 == n)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }
    int dp1(){
        int i, len, pos;
        b[1] = a[1];
        len = 1;
        for(i = 2; i <= n; i++){
            if(a[i] >= b[len]){
                len += 1;
                b[len] = a[i];
            }
            else {
                pos = lower_bound(b+1, b+1+len, a[i]) - b;
                b[pos] = a[i];
            }
        }
        return len;
    }
    int dp2(){
        int i, len, pos;
        b[1] = a[n];
        len = 1;
        for(i = n-1; i >= 1; i--){
            if(a[i] >= b[len]){
                len += 1;
                b[len] = a[i];
            }
            else {
                pos = lower_bound(b+1, b+1+len, a[i]) - b;
                b[pos] = a[i];
            }
        }
        return len;
    }

以下为Accepted代码

#include <cstdio>
    #include <algorithm>
    
    using namespace std;
    
    int n, a[100004], b[100004];
    
    int dp1();
    int dp2();
    int s(int num, int l, int h);
    
    int main(){
        int T, i;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            for(i = 1; i <= n; i++)
                scanf("%d", &a[i]);
            int x1 = dp1();
            int x2 = dp2();
            if(x1 == n-1 || x1 == n || x2 == n-1 || x2 == n)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }
    int dp1(){
        int i, len, pos;
        b[1] = a[1];
        len = 1;
        for(i = 2; i <= n; i++){
            if(a[i] >= b[len]){
                len += 1;
                b[len] = a[i];
            }
            else {
                pos = upper_bound(b+1, b+len+1, a[i]) - b;
                //pos = lower_bound(b+1, b+len+1, a[i]) - b;
                //pos = s(a[i], 1, len);
                b[pos] = a[i];
            }
        }
        return len;
    }
    int dp2(){
        int i, len, pos;
        b[1] = a[n];
        len = 1;
        for(i = n-1; i >= 1; i--){
            if(a[i] >= b[len]){
                len += 1;
                b[len] = a[i];
            }
            else {
                pos = upper_bound(b+1, b+len+1, a[i]) - b;
                //pos = lower_bound(b+1, b+len+1, a[i]) - b;
                //pos = s(a[i], 1, len);
                b[pos] = a[i];
            }
        }
        return len;
    }
    int s(int num,int l,int h)  
    {  
        int mid;  
        while(l<=h)  
        {  
            mid=(l+h)/2;  
            if(num>=b[mid])  
                l=mid+1;  
            else h=mid-1;  
        }  
        return l;  
    }

[Link 1]: http://blog.csdn.net/nyist_tc_lyq/article/details/51248180