羽猫球比赛题解

· · 个人记录

可爱的题目捏（虽然也和我有点关系）

根据题目可以了解到，本题需要找一个最长不下降子序列

然后开始看数据范围

10\%

对于10\%的数据, n=1所以只需要输出1就可以拿10分！(好耶)

30\%

然后对于30\%的数据, n\le 20此时好像没有什么可以光速骗分的步骤了，于是需要稍加思索。、

不难发现只需要把所有的子序列全部找出来然后再判断哪一个子序列是最长不下降子序列就好啦！

而此时对于每一位上的数只有两种状态，属于此子序列和不属于此子序列，因此最多也就是有2^n=2^{20}\le 10^9好像完全可以过掉30\%的数据(事实证明确实能过掉30\%)。

#include<bits/stdc++.h>\\30标程
using namespace std;

int n;
int a[40];

int bas[40],cnt,ans;
void searchAns(int loc){

    if(loc>n){
        ans=max(ans,cnt);
        return ;
    }
    if(a[loc]>=bas[cnt]){
        bas[++cnt]=a[loc];
        searchAns(loc+1);
        cnt--;
    }
    searchAns(loc+1);
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    searchAns(1);
    cout<<ans;
    return 0;
}

60\%

此时不难发现, 2^{n}>10^9所以暴力过不去力（呜呜）

但是n=5000却是一个很好的提示，他告诉了最多能用n^2=5000^2<10^9的程序过掉

那么问题又来了，这个n^2到底要怎么思考呢？首先肯定有一个n是遍历这n个数，那么剩下的一个n是要干什么呢(?

等一下，如果我们在遍历完一个数的时候能留下一个和答案有关的信息，后一个数遍历的时候再去查看留下的信息，这样不正好是\sum\limits_{i=1}^n i=\frac{n(n+1)}{2}吗？

那需要留下什么信息呢（？

如果是和答案有关的话，那记录下从第一位到遍历的这位之间的最长不下降子序列如何呢（？

稍加思索发现这样并不好，因为这样会丢失信息与遍历的这个数之间的关系，只留下了信息与位数之间的关系。

所以只需让这个信息代表的是选取这位后的这段区间的最长不下降子序列就好啦

那么我们记录信息的数组就是dp, 根据以上思考可以得到dp[loc]=\max\limits_{1\le i<loc}\left\{1+(a[i]\le a[loc]?dp[i]:0)\right\}

这也就是传说中的动态规划(dp), 详情请参考运筹学教材

#include<bits/stdc++.h>
using namespace std;

int n;
int a[5200];

int dp[5200];
//dp[从1到i最长不下降子序列(必选i)]
//dp[loc]=max{1+(a[loc]>=a[i]?dp[i]:0)} 
int ans;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    dp[1]=1;
    for(int loc=2;loc<=n;i++)
        for(int i=1;i<loc;i++)
            dp[loc]=max(dp[loc],1+(a[i]<=a[loc]?dp[i]:0));

    for(int i=1;i<=n;i++)
        ans=max(ans,dp[i]);
    cout<<ans;

    return 0;
}

100\%

我们已经攻克60\%的难题，对于100\%的数据，不难有一个想法就是能否加快更新答案时候的速度，使其能尽量不更改思路的情况下完成60\%\rightarrow100\%的转变。

但是很显然的是，小中野并没有想出来如何不更改dp过程就能优化的 (事实上除了100%的做法其他都是小中野现想出来的)

但是话又说回来，我们是否可以用dp数组的长度来代表答案,dp数组记录第i位上的数字？ 就像Abol变换是将横向求和变成了列向求和一样

这么做的话我们最终只需要输出dp数组的长度就可以了O.O

如果到这里都可以接受的话，那我相信你可以理解，dp数组最终是什么样子我们可能并不关系，我们只关心dp数组的长度。换句话说，我们在进行从第i个数到第i+1个数的时候，只关心dp数组最后一位上的数是什么（因为这关系到dp数组会不会变长）

那么我们考虑一组数据

8\\ 5\;6\;7\;1\;2\;4\;5\;3

对于这组数据，一眼1\;2\;4\;5为最长不下降子序列

但是我们要怎么转移呢？

很显然如果只有前3项的话，dp为[5\;6\;7]但是接下来的1要如何插入（？

如果你还记得之前说的，我们只关心dp数组的长度和dp数组的最后一位的话，那么这个问题很好解决，只需要把5换成1不就好了吗？也就是遍历到原数组的第4位的时候, dp数组为[1\;6\;7]

同理遍历到原数组第6位的时候dp数组为[1\;2\;4]此时要遍历5这个数, 只需要把dp[++]就得到了dp[]=[1\;2\;4\;5]

而对于最后一个数，我们只需要进行更改就可以了， 此时dp[]=[1\;2\;3\;5]

所以最长不下降子序列长度为4

但是要注意最长不下降子序列并不为1235而是1245

说到这里，我们不难写出dp递推方程：如果a[i]>=dp[ans]\Rightarrow dp[++ans]=a[i] 否则dp[k]=a[i] 其中dp[k]为dp数组中第一个大于a[i]的数

观察上式可以看出, 这还是一个n^2的递推，依旧过不了100\%的数据

但是你先别急，这个递推式和60\%的递推式的区别就是，这次的dp数组是一个单调不降的数组，而a[i]>=dp[ans]的时候是一个O(1)更改，最终需要优化的dp[k]=a[i]为从单调数组里查找一个数的操作

这个操作的优化方式已经很显然了，但是这里还是要先按下不表

不知道各位玩没玩过一个游戏: 在1-1000内任一想一个数，这个数必定可以用至多7次询问查询出来

没错，方法就是二分法，本题的这个优化和上边这个小游戏是几乎一模一样的，我们只需要对这个单调的dp数组进行二分查询，来确定大于a[i]的最小的数在哪里就可以啦，这是log\;n的，所以总复杂度就是n\log\;n

#include<bits/stdc++.h>
#define itn int
#define lli long long int
#define cs 1000200
using namespace std;

lli n,a[cs],ans;
lli dp[cs];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dp[ans=1]=a[1];
    for(int i=2;i<=n;i++){
        if(a[i]>=dp[ans])
            dp[++ans]=a[i];
        else
            dp[upper_bound(dp+1,dp+1+ans,a[i],less<int>())-dp]=a[i];\\upper_bound为C艹内置的二分查抄函数，可以自行百度了解
    }
    cout<<ans;
    return 0;
}