本文主要是介绍UVA 103--- Stacking Boxes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题在小白书中的分类是动态规划，把题AC了之后在网上看解题报告后，多数解法也是DAG上的动态规划。但其实一个简单的深度优先就能解决问题了。首先将每数从大到小排序，再将各组按照排序后的第一个数字的大小进行从大到小排序。需要注意的是，记录各组数据的编号也要和数进行同步的排序。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int k,n;
int anscnt;
int vis[30+5];
vector <vector<int> > box;
vector <int> order;//记录各组数的序号
vector <int> ans;bool cmp(int i,int j){return i>j;}
bool vcmp(vector<int> i,vector<int> j){return i[0]>j[0];}
bool ocmp(int i,int j){return box[i-1][0]>box[j-1][0];}
void dfs(int,int,int);int main()
{//freopen("data.txt","r",stdin);while(cin>>k>>n){vector <int> t;int x;box.clear();order.clear();for(int i=0;i<k;i++){t.clear();order.push_back(i+1);for(int j=0;j<n;j++){cin>>x;t.push_back(x);}sort(t.begin(),t.end(),cmp);//各组数从大到小排序box.push_back(t);}sort(order.begin(),order.end(),ocmp);//先将编号排序sort(box.begin(),box.end(),vcmp);//各组按照首数字的大小从大到小排序ans.clear();memset(vis,0,sizeof(vis));anscnt=0;dfs(0,0,-1);cout<<anscnt<<endl;for(int i=anscnt-1;i>=0;i--){cout<<ans[i];i==0?cout<<endl:cout<<" ";}}return 0;
}void dfs(int deep,int cnt,int prior)
{if(deep==k){if(cnt>anscnt){ans.clear();anscnt=cnt;for(int i=0;i<deep;i++) if(vis[i])ans.push_back(order[i]);}return;}if(prior==-1){//之前还未取任何一组数if(deep<k-1){dfs(deep+1,cnt,prior);vis[deep]=1;dfs(deep+1,cnt+1,deep);vis[deep]=0;}}else{int flag=1;for(int i=0;i<n;i++)if(box[deep][i]>=box[prior][i]) flag=0;if(flag==1){//当前这组数能被之前最后取的一组数装下vis[deep]=1;dfs(deep+1,cnt+1,deep);vis[deep]=0;}dfs(deep+1,cnt,prior);}return ;
}这篇关于UVA 103--- Stacking Boxes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
