题目链接：积木

分析

这题数据也太水了吧我喜欢

可以直接暴力搜索每一个积木的每一个顺序的每一种放置方法。
阶乘级别的复杂度，居然能过就离谱。

正解是状压DP。$f[i][j][k]$当中：$i$表示积木选择的状态，每一位的0/1表示这个积木有没有被选中，$j$表示最上面的那个积木，k表示哪一种放法（0，1，2）。

枚举$l,g$可以得出转移：

f[i|(1<<(l-1))][l][g]=max(f[i|(1<<(l-1))][l][g],f[i][j][k]+a[l][w[g][2]]);

上代码

暴搜

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;int n,a[20],b[20],c[20],v[20],mx;int pd(int x,int y,int xx,int yy)
{if(x<=xx&&y<=yy) return 1;else if(x<=yy&&y<=xx) return 1;return 0;
}void dfs(int x,int ans,int l,int w)
{mx=max(mx,ans);if(x==n) return;for(int i=1;i<=n;i++){if(!v[i]){if(pd(a[i],b[i],l,w)){v[i]=1;dfs(x+1,ans+c[i],a[i],b[i]);v[i]=0;}if(pd(a[i],c[i],l,w)){v[i]=1;dfs(x+1,ans+b[i],a[i],c[i]);v[i]=0;}if(pd(b[i],c[i],l,w)){v[i]=1;dfs(x+1,ans+a[i],b[i],c[i]);v[i]=0;}}}
}int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>b[i]>>c[i];}dfs(0,0,100000001,100000001);cout<<mx;return 0;
}

状压

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;int n,a[20][3],ans;
int f[1<<16][20][4];
const int w[3][3]={{0,1,2},{0,2,1},{1,2,0}};int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i][0]>>a[i][1]>>a[i][2];sort(a[i],a[i]+3);}f[0][0][0]=f[0][0][1]=f[0][0][2]=0;for(int i=0;i<=1<<n;i++){//j,k下面一个 for(int j=1;j<=n;j++){for(int k=0;k<=2;k++){if(i==(1<<n)-1) continue;//l,g下面一个 for(int l=1;l<=n;l++){if(i&(1<<(l-1))) continue;for(int g=0;g<=2;g++){if(a[l][w[g][0]]<=a[j][w[k][0]]&&a[l][w[g][1]]<=a[j][w[k][1]]){f[i|(1<<(l-1))][l][g]=max(f[i|(1<<(l-1))][l][g],f[i][j][k]+a[l][w[g][2]]);}ans=max(ans,f[i|(1<<(l-1))][l][g]);}}}}}cout<<ans;return 0;
}