Solution UVA: 103 - Stacking Boxes

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss103 - Stacking Boxes	Accepted	C++11	0.000	0.000	6303	1 mins ago

Suggest: 

- Method 1 using DFS and find Longest Path

- Method 2 using Dynamic Programming LIS (many people choice) {

+ Map index vector<int>

+ Sort vector<int>

+ Sort vector< vector<int>> with compare function

+ DP LIS with compare function another

+ Trace with last index

}

Code using method 2:

#include<bits/stdc++.h>

#define int long long

#define oo LLONG_MAX

#define FOR(i, a, b) for(int i=a; i<=b; i++)

using namespace std;

int n, m;

map<vector<int>, int> id;

bool cmp(vector<int> a, vector<int> b){

    for(int i=0; i<a.size(); i++)

        if (a[i] < b[i]) return true;

        else return false;

    return true;

}

bool smaller(vector<int> a, vector<int> b){

    for(int i=0; i<a.size(); i++)

        if (a[i] >= b[i]) return false;

    return true;

}

void f(int index, const vector<int> &par, vector< vector<int>> &a){

    if (index == -1) return;

    f(par[index], par, a);

    cout<<id[a[index]]<<" ";

}

void solve(){

    id.clear();

   

    vector< vector<int> > a(n, vector<int>(m));

    vector< int > F(n), par(n, -1);

   

    FOR(i, 0, n-1){

       

        FOR(j, 0, m-1) cin >> a[i][j];

        sort(a[i].begin(), a[i].end());

        id[a[i]] = i+1;

    }

    sort(a.begin(), a.end(), cmp);

    int res= -oo, index= 0;

    FOR(i, 0, n-1){

        FOR(j, 0, i-1)

            if (smaller(a[j], a[i])){

               

                if (F[i] < F[j] + 1) par[i] = j;

               

                F[i] = max(F[i], F[j] + 1);

               

               

                if (res < F[i]){                

                    res = F[i];

                    index = i;

                }

            }  

    }

    if (res==-oo) cout<<1<<"\n"; else cout<<res+1<<"\n";

    f(index, par, a);

    cout<<"\n";

}

int32_t main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    while(cin >> n >> m){

        solve();

    }

}