Comment

makoto: 2026-04-29 11:38:39

# 用二分搜索可以优化到nlogn

def bs(a, x, low, high):
    if low > high:
        return low
    mid = int((low+high)/2)
    if a[mid] == x: return mid
    elif a[mid] < x: return bs(a, x, low, mid-1)
    else: return bs(a, x, mid+1, high)


def solve(missle) -> None:
    m = len(missle)
    height = [0] * m    # 每个元素在哈斯图上的高度
    maxele = [0] * m    # 每层最大的元素
    maxheight = -1       # 当前哈斯图最大高度
    for i in range(m):
        x = missle[i]
        # 加入哈斯图
        idx = bs(maxele, x, 0, maxheight)
        if idx > maxheight:
            maxheight = idx
        height[i] = idx
        if maxele[idx] < x:
            maxele[idx] = x
    print(maxheight+1)


n = int(input())

for i in range(n):
    missle = list(map(int, input().split()[1:]))
    solve(missle)

Huhu_Miao: 2025-04-17 11:29:45

/**
 *    author:  Huhu_Miao
 *    created: 2025.4.17 11:28:00 (UTC+8)
**/

#include<iostream>
#include<algorithm>

int arr[101], dp[101];

void solve(){
	int N; std::cin >> N;
	for(int i = 0 ; i < N; i++) std::cin >> arr[i];
	dp[0] = 1;
	//LNIS
	for(int i = 1 ; i < N ; i++){
		int max = 1;
		for(int j = 0 ; j < i ; j++) if(arr[i] <= arr[j]) max = std::max(max, dp[j] + 1);
		dp[i] = max;
	}
	std::cout << *std::max_element(dp,dp+N) << '\n';
}

int main(){
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
	int T; std::cin>>T;
	while(T--) solve();
	return 0;
}

syl616: 2023-04-21 00:53:51

#include<iostream>
using namespace std;
int main()
{
	int time = 0;

	cin >> time;

	for (int i = 0; i < time; i++)
	{
		int max = 1; int min = 1;
		int numofelements = 0;
		cin >> numofelements;

		int* data = new int[numofelements + 1];
		data[0] = 0;

		int* result = new int[numofelements + 1];
		result[0] = 0;
		for (int i = 1; i <= numofelements; i++)
		{
			cin >> data[i];
		}
		for (int i = 1; i <= numofelements; i++)
		{
			result[i] = 1;
		}
		for (int i = 2; i <= numofelements; i++)
		{
			for (int j = 1; j < i; j++)
			{
				if (data[j] >= data[i])
				{
					result[i] = result[i] >= result[j] + 1 ? result[i] : result[j] + 1;
				}
			}
			max = max >= result[i] ? max : result[i];

		}

		cout << max << endl;

	}

}

222026: 2022-11-19 14:09:02

这不就是反过来的最长上升子序列吗？最后看的就是f[0]不是吗？ 为什么我这样写有问题呢？？

220214837: 2021-11-05 00:28:38

<script>alter("你电脑被黑了！")</script>

214861: 2021-10-24 13:51:10

题目上说的是以后每一发炮弹都不能高于前一发，实际上是以后每一发炮弹都低于前一发，相等也不行。

martinG: 2020-10-13 22:00:11

09的实例输出好像有问题呀，第一行能拦截的应该只有两个吧。这会导致测试数据里的问题吗？