听取WA10分声一片!求助“做练习”

[刘泽楷 (xiaoqingwa)]

以下是代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 11451;
int n,ans,last=INT_MAX;
int a[N];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a + n, greater<int>());
    for (int i = 0; i < n; i++)
    {
        if (a[i] <= last)
        {
            ans++;
            last = a[i];
        }
    }
    cout << ans << endl;
    return 0;
}

[anon86415901]

题目内容是啥

[刘泽楷 (xiaoqingwa)]

时间限制：1s 空间限制：512M

鱼大大在周末的时候经常会做一些练习题，但是他有一个习惯：题目呢，要做就先做难的，绝不回头解决以前的题！但是鱼大大患有多动症，长时间的练习会让他焦躁不安，心神逐渐飘远，这会导致鱼大大能解决的题目难度越来越低（简单）。而一道题目解决不出来，就失去了练习的意义。

羊大大也知道鱼大大这“无法解决比上一题难”的痛病，为了少让鱼大大感受社会的险恶，所以羊大大需要合理地让鱼大大练习题目，指定鱼大大做题目，只让鱼大大从难到易解决问题，问这样安排鱼大大最多能解决多少练习题？

【输入格式】

第一行一个整数n，表示题目总数量

第二行n个整数ai，分别表示每道题的难易程度

【输出格式】

一个整数表示鱼大大最多能练习的题目

【样例输入】

7
1 7 3 5 9 4 8
【样例输出】

3
说明：

从前往后，分别解决第2，4，6题，题目难度从7逐渐降到4，这样安排，鱼大大能解决的练习题目最多

1≤n≤10000

[刘泽楷 (xiaoqingwa)]

做练习 - 题目详情 - 信友队 (xinyoudui.com)

[白桐吉 (■ ꧁༻残缺ぁ神迹々龙つ随风༻꧂)]

为什么要排序

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

不能排序的呀

[白桐吉 (■ ꧁༻残缺ぁ神迹々龙つ随风༻꧂)]

这就是最长下降子序列

[anon86415901]

这不动态规划吗
最长不上升子序列

[刘泽楷 (xiaoqingwa)]

不排序50分…

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

你ans什么东西

[anon86415901]

从后往前求看看满足条件的最大值用数组统计
最后求最大值

[刘泽楷 (xiaoqingwa)]

要将所有题目按照难度从大到小排序，是因为鱼大大有一个习惯：题目呢，要做就先做难的，绝不回头解决以前的题。这意味着鱼大大只能从难度最大的题目开始解决，然后逐渐解决难度递减的题目。因此，我们需要将所有题目按照难度从大到小排序，然后从前往后遍历所有题目，这样才能满足鱼大大的习惯。

[白桐吉 (■ ꧁༻残缺ぁ神迹々龙つ随风༻꧂)]

哪来的题解？

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

6666，理解能力-114514分

[刘泽楷 (xiaoqingwa)]

没有题解

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

他甚至给你50分

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

你就最长上升子序列改个判断条件就能过了：

if(a[i]<=a[j])f[i]=max(f[i],f[j]+1);

[白桐吉 (■ ꧁༻残缺ぁ神迹々龙つ随风༻꧂)]

是的

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

给个解决方案

[杨晋华 (集贸)]

#include<bits/stdc++.h>
using namespace std;
int n,t,mas[10009],k[10009]; 
int main(){

    cin>>t;
    for(int i=1;i<=t;i++) cin>>mas[i];
    
    for(int i=1;i<=t;i++){
        k[i]=1;
    	for(int j=1;j<i;j++){
            if(mas[i]<=mas[j]&&k[j]+1>k[i])
                k[i]=k[j]+1;
        }
    }
  
    int maxn=k[1];
    for(int i=1;i<=t;i++){
        maxn=max(maxn,k[i]);
    }
    
    cout<<maxn;
    return 0;
}

其实就是求最长不上升子序列，那道题改一改就行