木棍加工

基礎dp題

先按 長度排序，長度相同的按寬度排序（貪心）。然后求關于寬度的不上升子序列覆蓋數

因為dilworth定理得（最小的）不上升子序列覆蓋數=最長上升子序列長度

所以求關于寬度的最長上升子序列即可

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; #define Maxn 5010 int n; struct node{int L,W; }a[Maxn]; int dp[Maxn]; bool cmp(node x,node y) {if(x.L==y.L)return x.W>=y.W;else return x.L>=y.L; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].L,&a[i].W);sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++)dp[i]=1;for(int i=1;i<=n;i++)for(int j=1;j<i;j++){if(a[j].W<a[i].W)dp[i]=max(dp[i],dp[j]+1);}int ans=0;for(int i=1;i<=n;i++)ans=max(ans,dp[i]);printf("%d",ans);return 0; }

轉載于:https://www.cnblogs.com/LianQ/p/11236989.html

總結

以上是生活随笔為你收集整理的木棍加工的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。