1 solutions

  • 0
    @ 2024-10-10 16:45:59

    每个人身高为a[i],分别记录当i作为队伍中最高的人时左边有几个人,右边几个人。

    ac code

    #include<bits/stdc++.h>
    typedef long long LL;
    using namespace std;
    
    int n,a[110],ans;
    int f[110],g[110];
    
    int main ()
    {
    	cin >> n;
    	for(int i = 1;i <= n;++ i)
    	{
    		cin >> a[i];
    	}
    	
    	for(int i = 1;i <= n;++ i)
    	{
    		f[i] = 1;
    		for(int j = 1;j < i;++ j)
    		{
    			if(a[j] < a[i])f[i] = max(f[i],f[j] + 1);
    		}
    	}
    	
    	for(int i = n;i >= 1;-- i)
    	{
    		g[i] = 1;
    		for(int j = n;j > i;-- j)
    		{
    			if(a[j] < a[i])g[i] = max(g[i],g[j] + 1);
     		}
    	}
    	for(int i = 1;i <= n;++ i)
    	{
    		ans = max(f[i] + g[i] - 1,ans);
    	}
    	cout << n - ans;
    	
    	
    	
    	
    	
    	
    	
    	return 0;
    }
    

    Information

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