1 solutions

  • 0
    @ 2024-9-10 13:35:18

    题解:

    题目要求,给一行数据,要把这些数据拆成尽可能长的几个下降序列;

    for(int i = 1;i <= n;++ i)
    {
    	int t = 1;
    	for(;t <= cnt;++ t)
    	{
    		if(a[i] <= c[t])break;
    	}
    	c[t] = a[i];
    	if(t > cnt)cnt ++;
    }
    

    假设目前开辟了cnt个数列,后面遇到的数我们就要么开辟新的要么放在旧的后面;

    ```#include<bits/stdc++.h>
    typedef long long LL;
    using namespace std;
    const int N = 1e5 + 10;
    
    int n,ans,cnt;
    int a[N],b[N],c[N];
    
    
    int main ()
    {
    	n = 1;
    	while(cin >> a[n])n++;
    	n --;
    	for(int i = 1;i <= n;++ i)
    	{
    		b[i] = 1;
    		for(int j = 1;j < i;++ j)
    		{
    			if(a[j] >= a[i])b[i] = max(b[i],b[j] + 1);
    		}
    		ans = max(ans,b[i]);
    	}
    	
    	for(int i = 1;i <= n;++ i)
    	{
    		int t = 1;
    		for(;t <= cnt;++ t)
    		{
    			if(a[i] <= c[t])break;
    		}
    		c[t] = a[i];
    		if(t > cnt)cnt ++;
    	}
    	
    	cout << ans << "\n" << cnt << "\n";
    	return 0;
    }
    • 1

    Information

    ID
    6865
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    10
    Tags
    (None)
    # Submissions
    1
    Accepted
    1
    Uploaded By