讨论 / 求题解啊
nie 2012-08-20 16:30:00
点我顶贴 收藏 删除
看了wish大牛的题解,我对维护单调队列的方法感到很神奇。

而我对爆搜感到更神奇。

但是又没人发题解,于是在这里求程序或者伪代码,当然有详细题解最好,希望有人尽快发上去。

#1 594250@2011-10-02 11:25:00
回复 删除
回复 楼主nie 的帖子

爆搜真的过了......

#2 ·August·@2011-10-03 11:59:00
回复 删除
20分。。。

#include<iostream>

#include<cstdio>

using namespace std;

int a[1000001],b[1000001],c[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);

}

#3 工藤柯南@2012-08-20 16:07:00
回复 删除
70分
#4 工藤柯南@2012-08-20 16:29:00
回复 删除
爆搜吧,满分

状态: Accepted

测评机: Xeost[5]

得分: 100分 [我要评价一下题目~]

提交日期: 2012-8-20 16:27:00

有效耗时: 3016毫秒

测试结果1: 通过本测试点|有效耗时187ms

测试结果2: 通过本测试点|有效耗时188ms

测试结果3: 通过本测试点|有效耗时172ms

测试结果4: 通过本测试点|有效耗时172ms

测试结果5: 通过本测试点|有效耗时437ms

测试结果6: 通过本测试点|有效耗时344ms

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

测试结果8: 通过本测试点|有效耗时469ms

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

测试结果10: 通过本测试点|有效耗时172ms

#5 工藤柯南@2012-08-20 16:30:00
回复 删除
核心

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;

查看更多回复
提交回复