UVa-103 : Stacking Boxes

問題概要

D(<10)次元の箱がN(<30)個ある。箱を入れ子にして最大いくつ詰めることができるか求める問題。どの順に積めるかも出力する。

解法

ソートして順序を適切に定めた上でLIS。

acceptされたコード

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

struct box{
	vector<int> ls;
	int idx;
};

bool operator<(const box& lhs, const box& rhs){
	return lhs.ls < rhs.ls;
}

const int MAX_N = 30;
int D, N;

box bs[MAX_N + 1];

int dp[MAX_N + 1];
int prev[MAX_N + 1];

bool init(){
	if(scanf("%d%d", &N, &D)==EOF){
		return false;
	}

	for(int i=0; i<N; i++){
		vector<int> tmp;
		for(int j=0; j<D; j++){
			int x;
			scanf("%d", &x);
			tmp.push_back(x);
		}
		sort(tmp.begin(), tmp.end());
		bs[i] = (box){tmp, i + 1};
	}

	return true;
}

bool strict_large(const box& lhs, const box& rhs){
	for(int i=0; i<D; i++){
		if( !(lhs.ls[i] > rhs.ls[i]) ){
			return false;
		}
	}
	return true;
}

void solve(){
	memset(dp, 0, sizeof(dp));
	bs[N] = (box){vector<int>(D, -1), 0};
	sort(bs, bs + N + 1);
	for(int i=0; i<N+1; i++){
		for(int j=0; j<D; j++){

		}
	}
	for(int i=0; i<N+1; i++){
		for(int j=i+1; j<N+1; j++){
			if(strict_large(bs[j], bs[i]) &&  dp[j] < dp[i] + 1){
				dp[j] = dp[i] + 1;
				prev[j] = i;
			}
		}
	}

	int *p = max_element(dp, dp + N + 1);
	int last = p - dp;
	printf("%d\n", *p);
	vector<int> ans;
	for(int i=0; i<*p; i++){
		ans.push_back(bs[last].idx);
		last = prev[last];
	}
	for(int i=(int)ans.size() - 1; i>=0; i--){
		printf("%d%c", ans[i], i?' ':'\n');
	}
}

int main(){
	while(init()){
		solve();
	}

	return 0;
}