C 解法, 执行用时: 2ms, 内存消耗: 272K, 提交时间: 2023-07-17 22:39:31

#include<stdio.h>

int main()//Dilworth定理
{
	int max1=0,max2=0,a[100001],dp[100001],dp1[100001],i=1,j,k;
	while(scanf("%d",&a[i])!=EOF) i++;
	i--;	
	for(j=1;j<=i;j++)
	{dp[j]=1;dp1[j]=1;
		for(k=1;k<j;k++)
		{
			if(a[k]>a[j])
			{
				dp[j]=dp[j]>dp[k]+1?dp[j]:dp[k]+1;
			}
			else
			{
				dp1[j]=dp1[j]>dp1[k]+1?dp1[j]:dp1[k]+1;
			}
		}
		max1=dp[j]<max1?max1:dp[j];
		max2=dp1[j]<max2?max2:dp1[j];
	}
	printf("%d\n%d\n",max1,max2);
}

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 432K, 提交时间: 2023-02-12 21:34:45

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

int f[114514],s[114514];

int main()
{
    ios::sync_with_stdio(0);
    int ans=0,res=0;
    int x;
    while(cin>>x)
    {
        int p=lower_bound(s,s+res,x)-s;
        if(p==res) s[res++]=x;
        else s[p]=x;
        p=upper_bound(f,f+ans,x,greater<int>())-f;
        if(p==ans) f[ans++]=x;
        else f[p]=x;
    }
    cout<<ans<<"\n"<<res;
    return 0;
}

Python2 解法, 执行用时: 12ms, 内存消耗: 3104K, 提交时间: 2021-11-21 11:43:26

import sys
arr = sys.stdin.readlines()
ar = arr[0].strip().split()
n = len(ar)

dp = [1] * n 
dp2 = [1] * n 

for i in range(1,n):
    max_ = 0
    for j in range(i):
        if int(ar[j]) > int(ar[i]):
            max_ = max(max_,dp[j])
        else:
            dp2[i] = max(dp2[i],dp2[j]+1)
    dp[i] = max_ + 1

print(max(dp))
print(max(dp2))

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 392K, 提交时间: 2022-10-10 16:09:56

#include<iostream>
using namespace std;
int n=1,v1,v2;
int a[110];
int f[110],g[110];
int main()
{
	while(cin>>a[n])n++;
	n--;
	for(int i=1;i<=n;i++){
		f[i]=g[i]=1;
		for(int j=1;j<i;j++){
			if(a[i]<=a[j])f[i]=max(f[i],f[j]+1);
			else g[i]=max(g[i],g[j]+1);
		}
		v1=max(v1,f[i]);
		v2=max(v2,g[i]);
	}
	cout<<v1<<endl<<v2;
    return 0;
}

pypy3 解法, 执行用时: 75ms, 内存消耗: 21528K, 提交时间: 2023-05-25 19:35:34

arr = list(map(int, input().split()))

n = len(arr)

dp0 = [1]*n
dp1 = [1]*n
for i in range(n):
    for j in range(i):
        if arr[i]<=arr[j]:
            dp0[i] = max(dp0[i], dp0[j]+1)
        else:
            dp1[i] = max(dp1[i], dp1[j]+1)
            
print(max(dp0))
print(max(dp1))
    

Python3 解法, 执行用时: 40ms, 内存消耗: 4600K, 提交时间: 2022-07-06 16:49:50

l = [int(s) for s in input().split()]
n = len(l)
dp1 = [1]*n
dp2 = [1]*n
for i in range(n):
    for j in range(i):
        if l[j] > l[i]:
            dp1[i] = max(dp1[i],dp1[j] + 1)
        else:
            dp2[i] = max(dp2[i],dp2[j] + 1)
print(max(dp1))
print(max(dp2))