题目描述

输入

输出

样例输入

3

8 7 6

3 9 4

1 10 5

输出

18

数据范围

样例解释

解法

容易从n<=15得出可以使用状态压缩动态规划。

设f[i][j][k]表示01状态为i，最后一个放的是第j个积木，最后放的积木按第k种方式来摆放。摆放方式有3种，长 宽、长 高、宽 高。

转移方程显然。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define ll long long

#define sqr(x) ((x)*(x))

#define ln(x,y) int(log(x)/log(y))

using namespace std;

const char* fin="aP2.in";

const char* fout="aP2.out";

const int inf=0x7fffffff;

const int maxn=17,maxk=1<<maxn;

const int w[3][3]={{0,1,2},{0,2,1},{1,2,0}};

int n,i,j,k,l,o;

int a[maxn][3];

ll f[maxk][maxn][3];

ll ans;

int main(){

    scanf("%d",&n);

    for (i=1;i<=n;i++){

        scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);

        sort(a[i],a[i]+3);

    }

    for (i=0;i<1<<n;i++)

        for (j=1;j<=n;j++)

            for (k=0;k<3;k++){

                if (i==((1<<n)-1)) continue;

                for (l=1;l<=n;l++){

                    if (i&(1<<(l-1))) continue;

                    for (o=0;o<3;o++){

                        if (a[l][w[o][0]]<=a[j][w[k][0]] && a[l][w[o][1]]<=a[j][w[k][1]]){

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

                            ans=max(ans,f[i|(1<<(l-1))][l][o]);

                        }

                    }

                }

            }

    printf("%lld",ans);

    return 0;

}

启发

n很小时考虑状态压缩动态规划。