而我对爆搜感到更神奇。
但是又没人发题解,于是在这里求程序或者伪代码,当然有详细题解最好,希望有人尽快发上去。
#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);
}
状态: 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
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;