P1094 （C语言代码）

解题思路:

                砍成1X1的单位方块，需要 n*m-1 刀。

                如果说，横、纵方向的每一刀的代价都一样的话。那很简单，n方向最少砍n-1刀，同理m方向最少要砍m-1刀，（自己画图看看）。那么剩余的那几刀分给代价最少的去砍，

                min=(n-1)*n的代价+(m-1)*m的代价+(n*m-n-m+2)*两者最小的代价

                当然，题目没有那么简单，它每一刀的代价可能都不同

                我的思路是这样子的:

                1.一刀两断，x方向砍了第一刀，如果y方向要砍，那么y要砍两刀，代价*2。当然同x方向不用

                2.既然是这样，那么代价高的就要少砍一些

                3.完毕！
注意事项:

                注意看题目，我相信很多人和我一样，以为只有4个输入。认真审题！每一刀它都可能会给你一个不一样的代价，输入案例真的有点坑人 2 2 3 3....

参考代码:

#include<stdio.h>
//用的是c,随便排一下序...
void sort(int a[],int len){
    for(int i=0;i<len-1;i++){
        int k=i;
        for(int j=i+1;j<len;j++){
            if(a[k]<a[j]){
                k=j;
            }
        }
        if(k!=i){
            a[i]=a[i]^a[k];
            a[k]=a[i]^a[k];
            a[i]=a[i]^a[k];
        }
    }
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    
    if(n==1&&m==1){
        printf("0");
        return 0;
    }
    
    int a[2000],b[2000];
    for(int i=0;i<n-1;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<m-1;i++){
        scanf("%d",&b[i]);
    }
    //对两个方向的代价排一下序
    sort(a,n-1);
    sort(b,m-1);
    
    int i=0,j=0;      //用于记录a,b数组的下标
    int comt=0;      //总代价 
    int x=1,y=1;    //两个方向砍出来的木板数量
    
    while(i<n-1&&j<m-1){
        if(a[i]>b[j]){    //谁大谁先砍
            comt+=a[i]*y; //这里是乘以对面方向的块数
            i++;
            x++;          //砍完一刀当然是数量增加啦
        }else{
            comt+=b[j]*x;
            j++;
            y++;
        }
    }
    if(i==n-1){            //处理一下上面的尾款...
        for(;j<m-1;j++){
            comt+=b[j]*x;
            y++;
        }
    }else{
        for(;i<n-1;i++){
            comt+=a[i]*y;
            x++;
        }
    }
    printf("%d",comt);
}