my approach is to create 3 rotations for each box and sort the boxes according to increasing base area.
Then run LIS on the sorted data.
it gives correct results for test samples in the problem , still getting WA.
Need help !!!!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
my approach is to create 3 rotations for each box and sort the boxes according to increasing base area.
Then run LIS on the sorted data.
it gives correct results for test samples in the problem , still getting WA.
Need help !!!!
Name |
---|
so the sum of heights of the blocks in LIS sequence is the maxheight .
may be i am wrong in my approach
hey thanks , got it
but just for discussion sake here is my code , can u find out the problem :
// babtower.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
typedef struct{
int length;
int width;
int height;
}s;
bool compare(const s& s1,const s& s2)
{
if((long long)(s1.length * s1.width) != (long long)(s2.length * s2.width));
return (s1.length * s1.width < s2.length * s2.width);
if(s1.width != s2.width)
return (s1.width < s2.width);
if(s1.length != s2.length)
return (s1.length < s2.length);
return s1.height < s2.height;
}
int main()
{
int i,j,k,l,n;
int a,b,c,t;
vector<s> v(200);
int best[200];
int pred[200];
vector<int> in(200);
while(cin>>n,!cin.eof())
{
if(n == 0)
break;
i = 0;
j = 0;
s temp;
getchar();
while(i < n)
{
cin>>a>>b>>c;
if( a < b)
{
temp.length = a; temp.width = b ; temp.height = c;
}
else
{
temp.length = b; temp.width = a ; temp.height = c;
}
v[j++] = temp;
if(a < c)
{
temp.length = a; temp.width = c ; temp.height = b;
}
else
{
temp.length = c; temp.width = a ; temp.height = b;
}
v[j++] = temp;
if(b < c)
{
temp.length = b; temp.width = c ; temp.height = a;
}
else
{
temp.length = c; temp.width = b ; temp.height = a;
}
v[j++] = temp;
i++;
}
for(i=0;i<j;i++)
{
best[i] = 1;
pred[i] = i;
}
sort(v.begin(),v.begin() +j,compare);
int maxheight = 0;
for(i=1;i < j;i++)
{
for(k =0;k< i;k++)
{
if(v[i].length > v[k].length && v[i].width > v[k].width)
{
if(best[i] < best[k] + 1)
{
best[i] = best[k] + 1;
pred[i] = k;
}
}
//cout<<best[i]<<endl;
}
}
int max=0;
int pos=-1;
for(i=0;i< j;i++)
{
if(max < best[i] ){
max = best[i];
pos = i;
}
}
int u , w;
for(u = max,w=pos;u--;w = pred[w])in[u] = w;
for(u =0;u< max;u++)
{
maxheight += v[in[u]].height;
}
cout<<maxheight<<endl;
}
return 0;
}