一道很简单的贪心题，排序后一直从横切花费和竖切花费中选较大的即可。
直接上代码（注：w[]表示每一切的花费，tot表示在这个方向上目前有几块，now表示现在选到了第几大的花费）

#include<iostream>
#include<algorithm>
using namespace std;
int t,n,m,totx,toty,nowx,nowy,ans;
int wx[10005],wy[10005];
int main()
{
    cin>>t;
    for(int k=1;k<=t;++k)
    {
        
    ans=0;
    totx=1;
    toty=1;
    cin>>n>>m;
    nowx=n-1;
    nowy=m-1;
    for(int i=1;i<=n-1;++i)
        cin>>wx[i];
    sort(wx+1,wx+n);
    for(int i=1;i<=m-1;++i)
        cin>>wy[i];
    sort(wy+1,wy+m);
    for(int i=1;i<=n+m-2;++i)
    {
        if(wx[nowx]>wy[nowy])
        {
            ans+=wx[nowx]*toty;
            totx++;
            nowx--;
        }
        else
        {
            ans+=wy[nowy]*totx;
            toty++;
            nowy--; 
        }
     } 
     cout<<ans<<endl;
       
    }
    return 0;
}
    

直接DP60分

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
bool c1(int a,int b){ return a>b; }
int n,m,a[10010],b[10010],f[10010][10010];
int main(){ int T;scanf("%d",&T);
    while(T--){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i) scanf("%d",a+i);
    for(int i=1;i<m;++i) scanf("%d",b+i);
    sort(a+1,a+n,c1); sort(b+1,b+m,c1);
    f[0][0]=0;
    for(int i=0;i<n;++i) 
    for(int j=0;j<m;++j){
        if(i&&j) f[i][j]=min(f[i-1][j]+a[i]*(j+1),f[i][j-1]+b[j]*(i+1));
        else if(i) f[i][j]=f[i-1][j]+a[i]*(j+1);
        else if(j) f[i][j]=f[i][j-1]+b[j]*(i+1);
    }
    printf("%d\n",f[n-1][m-1]);
}}

贪心100分

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m,a[10010],b[10010];
int main(){ 
    int T;scanf("%d",&T);
    while(T--){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i) scanf("%d",a+i);
    for(int i=1;i<m;++i) scanf("%d",b+i);
    sort(a+1,a+n); sort(b+1,b+m);
    int x=1,y=1,sm=0;
    for(n--,m--;n||m;){
        if(a[n]>b[m]) sm+=y*a[n--],x++;
        else sm+=x*b[m--],y++;
    }
    printf("%d\n",sm);
}}

不是很懂。。。。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    //freopen("travel.in","r",stdin);
    //freopen("travel.out","w",stdout);
    int t;cin>>t;
    while(t--)
    {
    int m,n,mm[55]={0},nn[55]={0},c,ans=0,ml=1,nl=1;
    cin>>n>>m;
    for(int i=1;i<n;i++) {cin>>c;nn[c]++;}
    for(int i=1;i<m;i++) {cin>>c;mm[c]++;}
    for(int i=50;i>=1;i--)
    {
        while(mm[i]!=0||nn[i]!=0)
        {
            if(mm[i]!=0) {mm[i]--;ans+=i*nl;ml++;}
            if(nn[i]!=0) {nn[i]--;ans+=i*ml;nl++;}
        }
    }
    
    cout<<ans<<endl;
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

一开始想错算法了，555把代码全删了。。。
不过这是我为数不多的提交一次就AC的题。。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int T,n,m,s,ans,cutx,cuty,k,i,j,x[10003],y[10003];

inline int read()//快读
{
int ee=0,ff=1;
char ss=getchar();
while((ss<'0'||ss>'9')&&ss!='-')ss=getchar();
while((ss>='0'&&ss<='9')||ss=='-')
{
if(ss=='-')ff=-1;
else ee=ee*10+ss-'0';
ss=getchar();
}
return ee*ff;
}

int cmp(int a,int b)
{
return a>b;
}

int main()
{
T=read();
for(s=1;s<=T;s++)
{
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
ans=0;
n=read();m=read();
for(i=1;i<n;i++)x[i]=read();
for(i=1;i<m;i++)y[i]=read();
std::sort(x+1,x+n,cmp);
std::sort(y+1,y+m,cmp);

i=1;//X切到第几刀
j=1;//Y切到第几刀
cutx=1;//X被切成几块
cuty=1;//Y被切成几块

for(k=1;k<=(m+n-2);k++)
{

if(x[i]>=y[j])//贪心，优先切代价大的；
{
ans+=x[i]*cuty;
i++;
cutx++;//切完后造成的结果
}
else
{
ans+=y[j]*cutx;
j++;
cuty++;
}
}
cout<<ans<<endl;
}
return 0;
}

最关键的是代价<=50，所以保存代价就行了。
贪心：从最大代价开始看。对于同样代价的边，横纵相交错着切，切完了一种方向的再把另一种方向剩的全切了。然后再看代价--的边。

自己蠢的呀批。一开始写初始化sum[0]顺手写成sum[2]，然后/两个放一起去了还只开1w。调了半天，贡献5次WA//哎~

贴一发代码

测试数据 #0: Accepted, time = 0 ms, mem = 716 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 716 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 712 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 716 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 716 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 712 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 712 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 712 KiB, score = 10

测试数据 #8: Accepted, time = 31 ms, mem = 712 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 712 KiB, score = 10

Accepted, time = 91 ms, mem = 716 KiB, score = 100
代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 20005
#define INF 0x7fffffff
using namespace std;

int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}

int T,n,m,ans;
int sum[2];

class node{
public:
int x,y;
}e[N];

bool operator <(node a,node b){
return a.x>b.x;
}

int main()
{
T=read();
while(T--)
{
n=read();
m=read();
for(int i=1;i<n;i++) e[i].x=read(),e[i].y=0;
for(int i=1;i<m;i++) e[i+n-1].x=read(),e[i+n-1].y=1;
sort(e+1,e+1+n+m-2);
sum[1]=sum[0]=ans=0;
for(int i=1;i<=n+m-2;i++)
{
ans+=e[i].x*(sum[e[i].y^1]+1);
sum[e[i].y]++;
}
printf("%d\n",ans);
}
return 0;
}

要哭了T_T。。
多组数据忘记初始化。。。。
我的AC率啊T_T~~~
楼下正解，我给一下我的代码
```c++
评测结果
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 716 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 716 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 716 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 720 KiB, score = 10
测试数据 #4: Accepted, time = 46 ms, mem = 716 KiB, score = 10
测试数据 #5: Accepted, time = 93 ms, mem = 716 KiB, score = 10
测试数据 #6: Accepted, time = 203 ms, mem = 712 KiB, score = 10
测试数据 #7: Accepted, time = 421 ms, mem = 716 KiB, score = 10
测试数据 #8: Accepted, time = 375 ms, mem = 716 KiB, score = 10
测试数据 #9: Accepted, time = 406 ms, mem = 720 KiB, score = 10
Accepted, time = 1574 ms, mem = 720 KiB, score = 100
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
long long h[10001],s[10001],n,m;
long long b1=1,b2=1;
bool cmp(long long x,long long y)
{
return x>y;
}
int main()
{
long long t;
cin>>t;
for (int k=1;k<=t;k++)
{
long long ans=0;
cin>>n>>m;
for (long long i=1;i<n;i++)
cin>>h[i];
for (long long i=1;i<m;i++)
cin>>s[i];
sort(h+1,h+n,cmp);
sort(s+1,s+m,cmp);
long long x1=1,x2=1;
while (x1<n || x2<m)
{
if (x1>=n)
ans+=b2*s[x2],x2++;
else if (x2>=m)
ans+=b1*h[x1],x1++;
else if (s[x2] < h[x1])
ans+=b1*h[x1],b2++,x1++;
else if (s[x2] >= h[x1])
ans+=b2*s[x2],b1++,x2++;
}
cout<<ans<<endl;
b1 = 1,b2 = 1;
}

return 0;
}
```

P1745 巧克力
贪心法，每次选代价最大的行获列来切。

设已经沿着列割了a刀，沿着行割了b刀。则将所有巧克力块沿
代价为x的列切开的总代价为x*(b+1)，沿
代价为y的行切开的总代价为y*(a+1)
易知，先切代价较小的行最后得到的总代价一定不会比先切代价较大的行最后得到的总代价小
所以代价较大的行应该先切(列同理)

现在假设代价最大的列代价为x，代价最大的行代价为y。(为了方便先不讨论切割其他行和列的情况)
那么先切x再切y的代价和 S1=x*(b+1)+y*(a+2)=x*b+x+y*a+y*2
先切y再切x的代价和S2=y*(a+1)+x*(b+2)=x*b+x*2+y*a+y
S1-S2得到 y-x 所以当y>x时 S1-S2>0 所以 S2的代价较小 也即先切y再切x的代价较小
同理 x>y时 先切x再切y的代价较小

将上面2点统一起来，就是每次都选择代价较大的行、列来切
Free Pascal Compiler version 2.6.2 [2013/02/12] for i386
Copyright (c) 1993-2012 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
69 lines compiled, 0.1 sec , 30464 bytes code, 1628 bytes data
测试数据 #0: Accepted, time = 0 ms, mem = 776 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 780 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 780 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 776 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 776 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 780 KiB, score = 10
测试数据 #6: Accepted, time = 62 ms, mem = 776 KiB, score = 10
测试数据 #7: Accepted, time = 140 ms, mem = 780 KiB, score = 10
测试数据 #8: Accepted, time = 156 ms, mem = 780 KiB, score = 10
测试数据 #9: Accepted, time = 156 ms, mem = 776 KiB, score = 10
Accepted, time = 545 ms, mem = 780 KiB, score = 100
###Block code
type list=array[1..10000] of int64;
var t,n,m,i,u,v,h,l:longint;
x,y:list;
ans:int64;
procedure qsort(var a:list;n:longint);
var i:longint;
procedure swap(var a,b:int64);
begin
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;
procedure adjust(s,m:longint);
var j,c:longint;
t:int64;
begin
t:=a[s];
j:=s;
c:=j shl 1;
while c<=m do begin
if (c<m)and(a[c]>a[c xor 1]) then c:=c xor 1;
if t<=a[c] then break;

a[j]:=a[c];
j:=c;
c:=j shl 1;
end;
a[j]:=t;
end;
begin
for i:=n shr 1 downto 1 do adjust(i,n);
for i:=n downto 2 do begin
swap(a[1],a[i]);
adjust(1,i-1);
end;
end;
procedure cutx;
begin
ans:=ans+x[u]*l;
inc(u);
inc(h);
end;
procedure cuty;
begin
ans:=ans+y[v]*h;
inc(v);
inc(l);
end;
begin
readln(t);
while t>0 do begin
readln(n,m);
for i:=1 to n-1 do readln(x[i]);
for i:=1 to m-1 do readln(y[i]);
qsort(x,n-1);
qsort(y,m-1);
h:=1;
l:=1;
u:=1;
v:=1;
ans:=0;
while (u<n)or(v<m) do begin
if u=n then cuty
else if v=m then cutx
else if x[u]>y[v] then cutx else cuty;
end;
writeln(ans);
dec(t);
end;
end.

P1745巧克力
Accepted

记录信息

评测状态 Accepted
题目 P1745 巧克力
递交时间 2014-11-05 21:33:14
代码语言 C++
评测机 上海红茶馆
消耗时间 1075 ms
消耗内存 700 KiB
评测时间 2014-11-05 21:33:16

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 640 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 644 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 640 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 640 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 636 KiB, score = 10

测试数据 #5: Accepted, time = 31 ms, mem = 640 KiB, score = 10

测试数据 #6: Accepted, time = 140 ms, mem = 668 KiB, score = 10

测试数据 #7: Accepted, time = 312 ms, mem = 692 KiB, score = 10

测试数据 #8: Accepted, time = 250 ms, mem = 700 KiB, score = 10

测试数据 #9: Accepted, time = 312 ms, mem = 700 KiB, score = 10

Accepted, time = 1075 ms, mem = 700 KiB, score = 100

代码

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

int t;
int n , m;
int i;
int a[10000 + 2];
int b[10000 + 2];
int totala , totalb;
int rolla , rollb;
int x , y;
long long ans;

void Qsort( int* a , int l , int r )
{
if( l >= r )
return;
int x = a[l];
int i = l;
int j = r;
while( i < j )
{
while( i < j && a[j] > x )
j--;
a[i] = a[j];
while( i < j && a[i] <= x )
i++;
a[j] = a[i];
}
a[i] = x;
Qsort( a , l , i - 1 );
Qsort( a , i + 1 , r );
return;
}

int main()
{

scanf( "%d" , &t );
while( t-- )
{
ans = 0;
scanf( "%d %d" , &n , &m );
memset( a , 0 , sizeof( a ) );
memset( b , 0 , sizeof( b ) );
for( i = 1 ; i < n ; i++ )
scanf( "%d" , &a[i] );
for( i = 1 ; i < m ; i++ )
scanf( "%d" , &b[i] );
Qsort( a , 0 , n - 1 );
Qsort( b , 0 , m - 1 );
totala = totalb = 0;
rolla = rollb = 1;
for( i = 1 ; i < n ; i++ )
totala += a[i];
for( i = 1 ; i < m ; i++ )
totalb += b[i];
x = n - 1;
y = m - 1;
/*while( 1 )
{
if( x <= 0 && y <= 0 )
break;
else if( x <= 0 )
{
ans += ( rolla++ ) * totalb;
break;
}
else if( y <= 0 )
{
ans += ( rollb++ ) * totala;
break;
}
else
if( totala > totalb )
{
ans += a[x] * rollb;
rolla++;
totala -= a[ x-- ];
}
else if( totala < totalb )
{
ans += b[y] * rolla;
rollb++;
totalb -= b[ y-- ];
}
else
if( a[x] > b[y] )
{
ans += a[x] * rollb;
rolla++;
totala -= a[ x-- ];
}
else
{
ans += b[y] * rolla;
rollb++;
totalb -= b[ y-- ];
}
}*/
while( 1 )
if( x <= 0 && y <= 0 )
break;
else if( x <= 0 )
ans += rolla * b[ y-- ];
else if( y <= 0 )
ans += rollb * a[ x-- ];
else
if( a[x] >= b[y] )
{
ans += a[ x-- ] * rollb;
rolla++;
}
else
{
ans += b[ y-- ] * rolla;
rollb++;
}
cout << ans << endl;
}
return 0;
}

第一次贪心为什么算法错误。。。

同楼下。。。inc（RP）；

多组数据，数组没有赋初值，导致t>1时快排各种凌乱。。。引以为戒攒人品，orz

同样的算法交了4次，前三次TLE90囧，最后一次终于A了

贪心，每次切行列中代价最大的即可。

注意比较的时候不要比较更新后的代价，比较最初的代价即可。。。

这就是0和AC的差别。。。

代码：

http://hi.baidu.com/samroxas/item/da6159cb9bf42f28ee4665e1

排序+贪心
一开始想出两种贪心方法的可以试试这组样例
1
3 3
1
2
3
3

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int  heng[10010],shu[10010];
long long ans[52];
int main()
{
    int t,i,j,a,b,n,m;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        long long sum=0;
        scanf("%d%d",&n,&m);
        a=n-1,b=m-1;
        heng[0]=-100000000;
        shu[0]=-100000000;
        for(j=1;j<n;j++)
        {
            scanf("%d",&heng[j]);
        }
        for(j=1;j<m;j++)
        {
            scanf("%d",&shu[j]);
        }
        sort(heng+1,heng+n);
        sort(shu+1,shu+m);
        while(a!=0||b!=0)
        if(heng[a]<shu[b])
        {
            sum+=shu[b]*(n-a);
            b--;
        }
        else
        {
            sum+=heng[a]*(m-b);
            a--;
        }
        ans[i]=sum;
        memset(heng,0,sizeof(heng));
        memset(shu,0,sizeof(shu));
    }
    for(i=1;i<=t;i++)
    {
        printf("%d\n",ans[i]);
    }
    return 0;
}