题目链接P1233 [ICPC 2001 Taejon R] 木棍加工 - 洛谷思路求一个数列中最长严格上升子序列的最大长度代码#includebits/stdc.h using namespace std; int n,ans 0; int main() { cin n; vectorpairint,int arr(n); for(int i 0;i n ;i) cin arr[i].first arr[i].second; auto cmp [](pairint,int a,pairint,int b){ if(a.first ! b.first)return a.first b.first; return a.second b.second; }; sort(arr.begin(),arr.end(),cmp); vectorint dp(n,1); for(int i 0;i n ;i) { for(int j 0;j i;j) { if(arr[i].second arr[j].second) dp[i] max(dp[i],dp[j] 1); } ans max(ans,dp[i]); } cout ans; return 0; }首先将数组以第一个键进行排序 这样就保证了长度在数列是严格递减的然后就是处理宽度的问题排完之后看宽度的序列。比如样例长度降序排完(5,2) (4,9) (3,5) (2,1) (1,4) 宽度序列 2 9 5 1 4现在的问题把这个序列分成尽量少的“不上升”子串。2, 1 ← 一条 9, 5, 4 ← 一条两条。所以答案是 2。为什么不升子串的条数 最长上升子序列的长度例子排好的序列 3 1 4 2 位置 0 1 2 3问题把这四个数分成尽量少的几堆每一堆从左往右不许上升只能递减或相等。先算一个东西每个位置“能被多长的上升串接上”记号dp[i]以第 i 个数结尾的、最长的上升子串有多长。i0数 3 前面没人光它自己 → dp 1 i1数 1 前面只有 33 比 1 大接不上 → dp 1 i2数 4 34 能接11214 能接112 → dp 2 i3数 2 12 能接1123、4 都比它大 → dp 2数 3 1 4 2 dp 1 1 2 2最大的 dp 是 2。所以最长上升子序列长度L 2比如3,4或者1,2。现在按 dp 的值分堆dp 1 的 3 1 dp 2 的 4 2看这两堆里面3 → 1 不上升 ✓ 4 → 2 不上升 ✓两堆每堆都合法。分完了。为什么“同一堆一定不上升”这是整件事的关键假设同一堆里出现了两个数后面的比前面的大... a ... b ... 且 a b且 dp 相同那 b 的 dp 怎么可能是同一个因为a bb 就能把“以 a 结尾的那条上升串”整个接过来长度是dp[a] 1。这比dp[b]大矛盾。所以同一堆里后面的数不可能比前面大。只能一路不增。这就是为什么“按 dp 分堆”是合法的。那堆数为什么正好是 Ldp的取值最小是 1最大是 L。所以最多只有 L 堆1、2、…、L。再看“为什么不能少于 L”找一条最长的上升子序列长度是 L。比如3, 4。这两个数能待在同一堆里吗不能。因为3 4是上升的——而同一堆里不许上升。所以这条 L 长的子序列里每个数都必须独占一堆。堆数 ≥ L。两边一夹堆数 ≥ L 上升子序列逼出来的 堆数 ≤ L 按 dp 分最多 L 堆 → 堆数 L知道这个后 这个题就简单了