_error404 @ 2024-03-26 19:45:46
原题链接：
H:可修改的最长上升子序列
虽然感觉没必要但还是把题目用markdown打一下方便各位直接在洛谷上看吧，顺便将公式变成Latex
题目描述
我们都做过基础的LIS问题，本题增加了可以在一定次数内修改数列的值进一步最大化LIS长度这一变动。
注意：这里的上升指的是严格单调上升，即相等的情况被排除在外。
现在给定一个长度为 n 的序列 x_1, …, x_n 并保证每一个 x_i 都是 [1, n] 中的整数。你可以对序列 x 进行不超过 m 次修改，每次修改都可以把任意一个 x_i 修改成 [1,n] 中的任意一个整数，而你的目标是最大化结果序列的最长上升子序列的长度。
你需要对 m = 0, …, n 这 n+1 种情况分别输出最大可能的最长上升子序列的长度。
输入
第一行输入一个整数 n (1 ≤ n ≤ 500) 表示序列长度。
第二行输入 n 个空格隔开的整数 x_1, …, x_n(1 ≤ x_i ≤ n)，表示初始序列。
输出
输出一行 n+1 个空格隔开的整数，分别表示 m = 0, …, n 时的答案。
样例输入
9
1 7 3 5 9 4 8 2 6
样例输出
4 5 6 7 8 8 8 9 9 9
看数据量感觉是O(n^3)的动规，但蒟蒻太菜了写不出，球球各位神犇指点一下辣QwQ