割とサクサク解けたのだが、参加が遅れたので順位が落ちました。
http://yukicoder.me/problems/no/497
問題
直方体の箱がN個あり、3辺の長さはX[i],Y[i],Z[i]である。
箱の向きを変えることができるとき、マトリョーシカ状に箱を入れ子にすると、最大何個まで入れ子にできるか。
解法
2つの箱を入れ子にするとき、片方の長い辺と片方の短い辺を合わせる意味はなく、それぞれ長い辺同士を合わせた方が入れ子にできる可能性がある。
よって、箱の向きをX[i]≦Y[i]≦Z[i]となるように回転させよう。
あとは(X[i],Y[i],Z[i])のtupleを昇順にソートしよう。
その場合、ソート順で手前の箱があとの箱を内包することはあり得ないので、箱iが箱j(j<i)を包めるかを順次判定しつつ入れ子の最大数を求めればよい。
int N; vector<vector<int>> V; int num[1010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>x>>y>>j; vector<int> R = {x,y,j}; sort(ALL(R)); V.push_back(R); num[i]=1; } sort(ALL(V)); int ma=1; FOR(i,N) { ma=max(ma,num[i]); for(j=i+1;j<N;j++) { if(V[i][0]<V[j][0] && V[i][1]<V[j][1] && V[i][2]<V[j][2]) { num[j]=max(num[j],num[i]+1); } } } cout<<ma<<endl; }
まとめ
今回は★3とはいえ実装も難易度も軽め。