题解 P1233 【木棍加工】

固执 · 2019-07-06 11:59:30 · 题解

思想：贪心 + DP

看大佬们太强了，题解我看不懂

这题一看就是贪心，因为题目讲了

先按长度排序，长度相同，按宽排序。 代码顺序：

int main() {
输入n、a[i]，对a[i]排序
dp并更新答案，覆盖ans
输出ans+1
结束
}

核心代码 dp:

for(int i=2; i<=n; i++) { //dp start
        for(int j=1; j<i; j++) { 
            if(a[j].r>a[i].r) {//判断
                dp[i]=max(dp[j]+1,dp[i]); //dp
            }
        }
        ans=max(dp[i],ans);//记录答案
}

于是，这题的大体思路就出来了~ 完整代码（请不要抄袭题解）：

#include<bits/stdc++.h>
using namespace std;
struct node {
    int l,r;
} a[11000];
int n;
int dp[11000]= {0},ans;
bool cmp(node x,node y) { //compare
    if(x.l==y.l) return x.r<y.r; //按长度排序，长度相同按宽度排序
    return x.l<y.l;
}
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i].l>>a[i].r; //输入
    sort(a+1,a+1+n,cmp);//排序
    for(int i=2; i<=n; i++) { //dp start
        for(int j=1; j<i; j++) {
            if(a[j].r>a[i].r) {//如果第j个木棍的宽大于第i个木棍的宽（类似于选择排序全部枚举一遍）
                dp[i]=max(dp[j]+1,dp[i]);//执行dp
            }
        }
        ans=max(dp[i],ans); //记录答案
    }
    cout<<ans+1; //最后加上1，因为至少有一种方案
    return 0; //end
}