UVa 437 The Tower of Babylon

``````for ( int i(1); i<=n; i++) {
d[i] = a[i].c;
for ( int j(1); j<i; j++) {
if (a[j].a<a[i].a && a[j].b<a[i].b && d[j]+a[i].c>d[i]){
d[i] = d[j] + a[i].c;
}
}
ans = max(ans, d[i]);
}``````

``````for ( int k(1); k<=n; k++){
for ( int i(1); i<=n; i++){
for ( int j(1); j<=n; j++) if (a[j].a>a[i].a && a[j].b>a[i].b && d[j]+a[i].c>d[i] ){
d[i] = d[j]+a[i].c;
}
}
}``````

AC确实没问题了，关键是复杂度抬高了一个数量级！

``````#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;

const int INF = 0x3fffffff;
const double eps = 1e-6;

struct NODE{
int a,b,c;
NODE(){}
NODE(int x,int y,int z): a(x),b(y),c(z) {}
}a[111];

bool cmp(NODE a,NODE b){
if (a.a==b.a) return a.b<b.b;
return a.a<b.a;
}
int d[111];

int I,T,n,m;

int main(){
freopen("in.txt","r",stdin);
while ( scanf("%d",&n) && n){
for ( int i(0); i<n; i++) {
int a1,b1,c1;
scanf("%d%d%d",&a1, &b1, &c1);
if (b1<a1) swap(a1,b1);
if (c1<b1) swap(b1,c1);
if (b1<a1) swap(a1,b1);
// printf("%d,%d,%d\n",a1,b1,c1);
a[i*3+1]=NODE(a1,b1,c1);
a[i*3+2]=NODE(a1,c1,b1);
a[i*3+3]=NODE(b1,c1,a1);
}
n*=3;
sort(a+1,a+n+1,cmp);
memset(d, 0, sizeof(d));
int ans = 0;
for ( int i(1); i<=n; i++) {
d[i] = a[i].c;
for ( int j(1); j<i; j++) {
if (a[j].a<a[i].a && a[j].b<a[i].b && d[j]+a[i].c>d[i]){
d[i] = d[j] + a[i].c;
}
}
ans = max(ans, d[i]);
}

printf("Case %d: maximum height = %d\n", ++I, ans);
}
return 0;
}``````

2022-12-17 23:57

01-15 19:36

2022-12-08 11:03

2022-12-10 17:21

2022-12-09 22:38

2022-12-10 18:47

2022-12-12 18:42