【DFS】【拓扑排序】【动态规划】Gym - 100642A - Babs' Box Boutique

给你10个箱子,有长宽高,每个箱子你可以决定哪个面朝上摆。把它们摞在一起,边必须平行,上面的不能突出来,问你最多摆几个箱子。

3^10枚举箱子用哪个面。然后按长为第一关键字,宽为第二关键字,从大到小排序。

如果前面的宽大于等于后面的宽,就连接一条边。

形成一张DAG,拓扑排序后跑最长路即可。

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int v[205],next[205],first[15],e;
void AddEdge(int U,int V){
v[++e]=V;
next[e]=first[U];
first[U]=e;
}
typedef pair<int,int> Point;
Point d[15];
int ans;
int a[15],b[15],c[15],cho[15],ru[15],f[15],n;
bool cmp(const Point &a,const Point &b){
return a.first!=b.first ? a.first>b.first : a.second>b.second;
}
void work(){
for(int i=1;i<=n;++i){
if(cho[i]==1){
d[i]=make_pair(max(a[i],b[i]),min(a[i],b[i]));
}
else if(cho[i]==2){
d[i]=make_pair(max(b[i],c[i]),min(b[i],c[i]));
}
else{
d[i]=make_pair(max(c[i],a[i]),min(c[i],a[i]));
}
}
e=0;
memset(first,0,sizeof(first));
memset(f,0,sizeof(f));
memset(ru,0,sizeof(ru));
sort(d+1,d+n+1,cmp);
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
if(d[j].second<=d[i].second){
AddEdge(i,j);
++ru[j];
}
}
}
queue<int>q;
for(int i=1;i<=n;++i){
if(!ru[i]){
q.push(i);
}
}
while(!q.empty()){
int U=q.front(); q.pop();
for(int i=first[U];i;i=next[i]){
f[v[i]]=max(f[U]+1,f[v[i]]);
--ru[v[i]];
if(!ru[v[i]]){
q.push(v[i]);
}
}
}
ans=max(ans,1+(*max_element(f+1,f+n+1)));
}
void dfs(int cur){
if(cur>n){
work();
return;
}
for(int i=1;i<=3;++i){
cho[cur]=i;
dfs(cur+1);
}
}
int main(){
int zu=0;
while(1){
++zu;
scanf("%d",&n);
if(n==0){
return 0;
}
for(int i=1;i<=n;++i){
scanf("%d%d%d",&a[i],&b[i],&c[i]);
}
ans=0;
dfs(1);
printf("Case %d: %d\n",zu,ans);
}
return 0;
}
上一篇:如何找出Xcode中不同版本Swift的路径


下一篇:Vijos P1023Victoria的舞会3【贪心+DFS求强联通分量】