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; }