Comment

hanser414627925: 2024-05-29 22:23:28

//最长单调不升子序列&&最长不下降子序列
#include<iostream>
using namespace std;
int main()
{
	int m, n;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> n;
		int a[100][2],max=1,k=0;
		for (int j = 0; j < n; j++)
		{
			a[j][0] = 1;
			cin >> a[j][1];
		}
		//最长单调不升子序列
		for (int j = 1; j < n; j++)
			for (int t = 0; t <j; t++)
					if (a[t][0]+1>a[j][0] && a[t][1] >= a[j][1])
					{
						a[j][0] = a[t][0] + 1;
						if (a[j][0] > max)max = a[j][0];
					}
		//最长不下降子序列
		for(int j = 0; j < n; j++)
			a[j][0] = 1;
		for (int j = 1; j < n; j++)
			for (int t = 0; t < j; t++)
				if (a[t][0] + 1 > a[j][0] && a[t][1] < a[j][1])//前面的导弹高度比后面的小的个数
				{
					a[j][0] = a[t][0] + 1;
					if (a[j][0] > k)k = a[j][0];
				}
		cout << max << ' '<<k<< endl;
	}
	return 0;
}

Westbrook: 2024-05-10 00:02:46

我个人对这个题的见解是，这个题是一道经典的dp问题，LIS（最长上升子序列），比方说，我们正着看，如果当前导弹能拦截，则后面比它小的导弹数都可以拦截，那其实反过来看就是上升子序列。至于多少套系统呢，一种解法是贪心，无非找到多少子序列，贪心的话枚举每一个序列的最后一个数字比较就好。或者有一个diworth对偶定理，其实系统数目就是该数组从前往后的最长上升子序列长度，故代码如下：#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 110;
int a[N];
int f[N];//f数组存储最长从最后一个到当前第i个导弹的最长上升子序列
int g[N];//存这一组数的最长上升子序列
int m, n;

int main()
{
	cin >> m;
	while (m--)
	{
		memset(a, 0,sizeof a);
		memset(f, 0, sizeof f);
		memset(g, 0, sizeof g);
		cin >> n;
		for (int i = 1; i <= n; i++)cin >> a[i];
		for (int i = n; i; i--)
		{
			f[i] = 1;
			for (int j = n; j > i; j--)
			{
				if (a[i] > a[j])
				{
					f[i] = max(f[i], f[j] + 1);
				}
			}
		}
		int res = 0;
		for (int i = 1; i <= n; i++)
		{
			res = max(res, f[i]);
		}
		int ans = 0;
		for (int i = 1; i <= n; i++)
		{
			g[i] = 1;
			for (int j = 1; 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(ans, g[i]);
		}
		cout << res << " " << ans << endl;
	}
	return 0;
}

nahgnez: 2024-01-15 19:54:33

# 之前的写得不对啦，看这里看这里

def insert(height, smallest_height):
    # 二分法查找
    left = 1
    right = len(smallest_height)
    while left < right:
        mid = (left + right) // 2
        if smallest_height[mid] > height:
            left = mid + 1
        else:
            right = mid
    if smallest_height[left] == height:
        smallest_height[left + 1] = height  # 刚好相等，后一位替换
    else:
        smallest_height[left] = height  # 不相等，替换


def blocked_missiles(heights):
    smallest_height = [30001]  # 零号位不使用
    for i in range(len(heights)):
        if heights[i] <= smallest_height[-1]:
            smallest_height.append(heights[i])
        else:
            insert(heights[i], smallest_height)
    return smallest_height


if __name__ == "__main__":
    # 学到一个新东西，狄尔沃斯定理：
    # 最长非升子序列的个数 = 最长非降子序列的长度
    n = int(input())
    for _ in range(n):
        heights = [int(x) for x in input().split()][1:]  # 第一个数字是长度，不需要
        smallest_height = blocked_missiles(heights)  # 计算被拦截的导弹数，也就是最长非升子序列
        reversed_question = blocked_missiles(heights[::-1])  # 最长非降子序列
        print(len(smallest_height) - 1, len(reversed_question) - 1)

nahgnez: 2024-01-15 19:38:51

def insert(height, smallest_height):
    # 二分法查找
    left = 1
    right = len(smallest_height)
    while left < right:
        mid = (left + right) // 2
        if smallest_height[mid] > height:
            left = mid + 1
        else:
            right = mid
    if smallest_height[left] == height:
        smallest_height[left + 1] = height  # 刚好相等，后一位替换
    else:
        smallest_height[left] = height  # 不相等，替换


def blocked_missiles(heights):
    smallest_height = [30001]  # 零号位不使用
    for i in range(len(heights)):
        if heights[i] <= smallest_height[-1]:
            smallest_height.append(heights[i])
        else:
            insert(heights[i], smallest_height)
    return smallest_height


if __name__ == "__main__":
    n = int(input())
    for _ in range(n):
        heights = [int(x) for x in input().split()][1:]
        num_blocked_missiles = []
        times = 0
        while True:
            times += 1
            smallest_height = blocked_missiles(heights)
            num_blocked_missiles.append(len(smallest_height) - 1)
            for i in range(1, len(smallest_height)):
                heights.remove(smallest_height[i])
            if len(heights) == 0:
                break
        print(num_blocked_missiles[0], times)

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

#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];

		}
	
		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;
				}
			}
			min = min >= result[i] ? min : result[i];

		}
		cout << max <<" "<<min<< endl;

	}
	
}

lin zehao: 2023-04-20 18:41:23

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    long long m, n, src;
    cin >> m;
    for (int i = 0; i < m; i++) {
        vector<int> num;
        num.clear();
        cin >> n;
        int count[100];
        int father[100];
        int flag[100];
        
        int need_num = 0;
        int temp_count = 0;

        for (int j = 0; j < n; j++) {
            cin >> src;
            num.push_back(src);
            flag[j] = 0;
        }
        while (temp_count < n)
        {   
            int temp = 0;
            int temp_num = 0;
            for (int j = 0; j < n; j++) {
                count[j] = 1;
                father[j] = j;
            }
            for (int j = 0; j < n; j++) {
                int temp = 0;
                int temp_father = j;
                if (flag[j] == 1) {
                    continue;
                }
                for (int k = 0; k < j; k++) {
                    if (flag[k] == 1) {
                        continue;
                    }
                    if (num.at(k) > num.at(j)) {
                        if (count[k] > temp) {
                            temp = count[k];
                            temp_father = k;
                        }
                    }
                }
                count[j] += temp;
                father[j] = temp_father;
            }


            for (int j = 0; j < n; j++) {
                if (flag[j] == 1) {
                    continue;
                }
                if (count[j] > temp) {
                    temp = count[j];
                    temp_num = j;
                }
            }
            if (temp_count==0) {
                cout << temp << " ";
            }
            while (father[temp_num] != temp_num)
            {
                temp_count++;
                flag[temp_num] = 1;
                temp_num = father[temp_num];
            }
            temp_count++;
            flag[temp_num] = 1;
            need_num++;
        }
        cout << need_num << endl;
        
    }
}