#include<iostream>

#include<cstdio>

using namespace std;

int a[1000001],b[1000001],c[1000001];

//int xm[1000001],ym[1000001],zm[1000001];

int g=0;//情况数

int n;

int Min(int aa,int bb)

{

if(aa<=bb) return aa;

return bb;

}

int fen(int ge,int xm,int ym,int zm);

int fen1(int ge,int xm,int ym,int zm);

int fen2(int ge,int xm,int ym,int zm);

int fen3(int ge,int xm,int ym,int zm);

int main()

{

int i;

// scanf("%d",&n);

cin>>n;

for(i=1;i<=n;i++)

{

scanf("%d%d%d",&a[i],&b[i],&c[i]);

}

int m=999999999;//最小值

m=Min(m,fen1(1,0,0,0));

m=Min(m,fen2(1,0,0,0));

m=Min(m,fen3(1,0,0,0));

cout<<m;

return 0;

}

int fen(int ge,int xm,int ym,int zm)//三科任选

{

int a1,b1,c1;

for(int i=ge;i<=n;i++)

{

if(a[i]<=xm||b[i]<=ym||c[i]<=zm) continue;

if(a[i]-xm>b[i]-ym && b[i]-ym<c[i]-zm) {ym=b[i];continue;}

if(a[i]-xm>c[i]-zm && c[i]-zm<b[i]-ym) {zm=c[i];continue;}

if(a[i]-xm<c[i]-zm && a[i]-xm<b[i]-ym) {xm=a[i];continue;}

if(a[i]-xm==c[i]-zm && a[i]-xm==b[i]-ym)

{

a1=fen1(i,xm,ym,zm);b1=fen2(i,xm,ym,zm);c1=fen3(i,xm,ym,zm);

if(a1<=b1&&a1<=c1) {xm=a[i];continue;}

if(a1>=b1&&b1<=c1) {ym=b[i];continue;}

if(a1>=c1&&b1>=c1) {zm=c[i];continue;}

}

if(a[i]-xm==b[i]-zm)

{

a1=fen1(i,xm,ym,zm);b1=fen2(i,xm,ym,zm);

if(a1<b1) {xm=a[i];continue;}

ym=b[i];continue;

}

if(a[i]-xm==c[i]-zm)

{

a1=fen1(i,xm,ym,zm);c1=fen3(i,xm,ym,zm);

if(a1<c1) {xm=a[i];continue;}

zm=c[i];continue;

}

if(b[i]-xm==c[i]-zm)

{

b1=fen2(i,xm,ym,zm);c1=fen3(i,xm,ym,zm);

if(b1<c1) {ym=b[i];continue;}

zm=c[i];continue;

}

}

return xm+ym+zm;

}

int fen1(int ge,int xm,int ym,int zm)//第ge个人 选第一科

{

xm=a[ge];

return fen(ge+1,xm,ym,zm);

}

int fen2(int ge,int xm,int ym,int zm)//第ge个人 选第二科

{

ym=b[ge];

return fen(ge+1,xm,ym,zm);

}

int fen3(int ge,int xm,int ym,int zm)//第ge个人 选第三科

{

zm=c[ge];

return fen(ge+1,xm,ym,zm);

}

回复 楼主·August· 的帖子

分情况1,2,3科，取增量最小的情况

如果每次增量相同，分情况搜

算法有问题么？

状态: Unaccepted

测评机： Xeost[5]

得分： 20分

提交日期： 2011-10-3 11:57:00

有效耗时： 469毫秒

测试结果1: 测试结果错误.错误结果为:93667069

正确结果应为:90149750

测试结果2: 测试结果错误.错误结果为:99617255

正确结果应为:97868468

测试结果3: 测试结果错误.错误结果为:99923256

正确结果应为:99544223

测试结果4: 测试结果错误.错误结果为:99934870

正确结果应为:99836692

测试结果5: 测试结果错误.错误结果为:103898502

正确结果应为:99998551

测试结果6: 测试结果错误.错误结果为:100286245

正确结果应为:99997953

测试结果7: 通过本测试点|有效耗时219ms

测试结果8: 测试结果错误.错误结果为:99999783

正确结果应为:99998985

测试结果9: 通过本测试点|有效耗时250ms

测试结果10: 测试结果错误.错误结果为:94809414

正确结果应为:79051766

procedure dfs(x,y,z,dep:longint);

begin

if dep>n then

begin

if x+y+z<ans then ans:=x+y+z;

exit;

end;

if (a[dep,1]<=x) or (a[dep,2]<=y) or (a[dep,3]<=z) then

begin

dfs(x,y,z,dep+1);

exit;

end;

if a[dep,1]+y+z<ans then dfs(a[dep,1],y,z,dep+1);

if x+a[dep,2]+z<ans then dfs(x,a[dep,2],z,dep+1);

if x+y+a[dep,3]<ans then dfs(x,y,a[dep,3],dep+1);

end;