• 欢迎光临~

P3173 [HAOI2009]巧克力

开发技术 开发技术 2022-07-20 次浏览
https://www.luogu.com.cn/problem/P3173
涉及知识点:贪心,排序
黄色题
 
思路:

STEP 1 条件整理

1.对一个长方形横着切n刀,竖着切m刀;

2.每一刀都要花费一定的代价;

3.如果巧克力从一个方向切了w块,那么从另一个方向切的时候就要花费w*x_ixi的代价;

4.问最小代价是多少。


STEP 2 题意分析

看见STEP 1里的条件4没有?盯着他看,使劲看!求最小啊!最优问题用什么?贪心!​

所以我们可以发现,越是靠后切,所要切的代价的倍数就越大,导致整体代价的上升。

贪心解决方案: 代价高的靠前切,代价小的靠后切


 

代码:

#include<bits/stdc++.h>//万能头棒棒
using namespace std;
int n,m,nh=1,ns=1;//分别记录n,m以及已切过的横刀数以及竖刀数
long long ans;//记录答案
struct node{
    int w,h;
}c[20001];//储存每一刀的结构体,w为代价,h为刀是横着切还是竖着切
int cmp(node x,node y){
    return x.w>y.w;
}//排序,从大到小
int main(){
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n-1;i++){
        scanf("%d",&c[i].w);
    }
    for (int i=n;i<=n+m-2;i++){
        scanf("%d",&c[i].w);
        c[i].h=1;//标记
    }//输入
    sort(c+1,c+n+m-1,cmp);//排序
    for (int i=1;i<=n+m-2;i++){
        if (c[i].h==0){
            ans+=c[i].w*ns;
            nh++;
        }else{
            ans+=c[i].w*nh;
            ns++;
        }
    }//执行公式
    printf("%lldn",ans);//输出
    return 0;//好习惯++
}

 

程序员灯塔
转载请注明原文链接:P3173 [HAOI2009]巧克力
喜欢 (0)