2019 计蒜之道 初赛 第三场 A题 淘宝商品价格大PK

原题地址
这道题题意就是找最长上升子序列长度在随机删除一个数后，输出最长上升子序列长度减少的数量。
大佬们说是很简单， 但身为菜鸟的我 ， 在比赛的时候连题目想要输出啥 ，都没明白。。。 所以理所当然的WA了好多发 之后放弃这道题， 在比赛结束之后 ， 问了一下大佬 ，然后大佬告诉我用最长上升子序列的板子 就行 。 至于最长上升子序列是什么 ， 请诸位移步这里。
附上刚刚明白如何做这道题的我的代码 ：

#include <bits/stdc++.h>
using namespace std;
int dp[110],a[110];
int b[110];
int f(int x)
{
    int len = 1,l,r,mid;
    dp[1] = a[1];
    for(int i=2;i<=x;i++)
    {
        l = 1;
        r = len;
        while(l <= r){
            mid = (l+r)/2;
            if(a[i] > dp[mid])
                l = mid + 1;
            else
                r = mid - 1;
        }
        dp[l] = a[i];
        if(l > len)
            len = l;
    }
    return len;
}
int f2(int x)
{
    int len = 1,l,r,mid;
    dp[1] = b[1];
    for(int i=2;i<=x;i++)
    {
        l = 1;
        r = len;
        while(l <= r){
            mid = (l+r)/2;
            if(b[i] > dp[mid])
                l = mid + 1;
            else
                r = mid - 1;
        }
        dp[l] = b[i];
        if(l > len)
            len = l;
    }
    return len;
}
int main()
{
    int n,ans,ans2,cnt = 0 ;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ans = f(n);
    for(int i=1;i<=n;i++)
    {
        int k = 0;
        ans2 = 0;
        memset(dp,0,sizeof(dp));
        for(int j=1;j<=n;j++)
        {
            if(j != i){
                b[++k] = a[j];
            }
        }
        ans2 = f2(n-1);
        if(ans2 != ans){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}