本文共 2033 字，大约阅读时间需要 6 分钟。

题目大意：有N个长方形，要穿过一张纸，最多可以在这张纸上剪掉K个长方形，剪掉一个长方形的代价为该长方形的长*宽

解题思路：首先，排除掉那个无用的长方形，无用的长方形指的是h[i] < h[j]且w[i] < [j]（h指长，w指宽），

因为w[i]递增，所以得到优化方程

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int N = 50010;typedef long long LL;const LL INF = 1LL << 60;struct Person{    LL w, h;}P[N];int n, k, flag;int que[N];LL dp[N][110];bool cmp(const Person &a, const Person &b) {    if (a.h == b.h) return a.w > b.w;    return a.h > b.h;}void init (){    for (int i = 1; i <= n; i++)        scanf("%lld%lld", &P[i].w, &P[i].h);    sort(P + 1, P + 1 + n, cmp);    int cnt = 1;    for (int i = 1; i <= n; i++)        if (P[cnt].w < P[i].w)            P[++cnt] = P[i];     n = cnt;    k = min(n, k);}LL getUp(int j, int k, int hole) {    return dp[j][hole] - dp[k][hole];}LL getDown(int j, int k) {    return P[j + 1].h - P[k + 1].h;}void solve() {    int head, tail;    for (int i = 1; i <= n; i++) dp[i][1] = P[i].w * P[1].h;    for (int hole = 2; hole <= k; hole++) {        head = tail = 0;        que[tail++] = 0;        for (int i = 1; i <= n; i++) {            while (head + 1 < tail && getUp(que[head + 1], que[head], hole - 1) <= P[i].w * getDown(que[head], que[head + 1]))                head++;            dp[i][hole] = dp[que[head]][hole - 1] + P[i].w * P[que[head] + 1].h;            while (head + 1 < tail &&  getUp(i, que[tail - 1], hole - 1) * getDown(que[tail - 2], que[tail - 1]) <= getUp(que[tail - 1], que[tail - 2], hole - 1) * getDown(que[tail-1], i))                tail--;            que[tail++] = i;        }    }    LL ans = dp[n][1];    for (int i = 2; i <= k; i++)        ans = min(ans, dp[n][i]);    printf("%lld\n", ans);}int main() {    while (scanf("%d%d", &n, &k) != EOF) {        init();        solve();    }    return 0;}
     
    
   

转载地址：https://blog.csdn.net/L123012013048/article/details/48947647 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！