JZOJ 4743. 积木

Description

Input

Output

Sample Input

3
8 7 6
3 9 4
1 10 5

Sample Output

18

Data Constraint

 

做法：几乎一看数据范围就可以猜出状态压缩dp，然而不知道为什么我打炸了。。于是该打记忆化搜索。

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #define rep(i,a,b) for (int i=1;i<=n;i++)

 #define M 65537

 #define N 17

 using namespace std;

 int a[N],b[N],c[N],n,ans;

 int f[M][N][];

 void Init(){

     scanf("%d",&n);

     rep(i,,n)    scanf("%d%d%d",&a[i],&b[i],&c[i]);

 }

 void Dfs(int dep,int x,int zt,int situ,int high){

     if (f[situ][x][zt]>=high) return;

     else f[situ][x][zt]=high,ans=max(ans,high);

     if (dep>n){

         ans=max(ans,high);

         return;

     }

     int cmpx,cmpy;

     if (zt==||zt==) cmpx=a[x]; else cmpx=b[x];

     if (zt==||zt==) cmpy=c[x]; else cmpy=b[x];

     if (cmpx<cmpy) swap(cmpx,cmpy);

     rep(i,,n){

         if (<<i&situ) continue;

         int xx=a[i],yy=b[i],next=;

         if (xx<yy) swap(xx,yy);

         if (xx<=cmpx&&yy<=cmpy) Dfs(dep+,i,next,situ|(<<i),high+c[i]);

         xx=a[i],yy=c[i],next=;

         if (xx<yy) swap(xx,yy);

         if (xx<=cmpx&&yy<=cmpy) Dfs(dep+,i,next,situ|(<<i),high+b[i]);

         xx=b[i],yy=c[i],next=;

         if (xx<yy)    swap(xx,yy);

         if (xx<=cmpx&&yy<=cmpy) Dfs(dep+,i,next,situ|(<<i),high+a[i]);

     }

 }

 void Work(){

     rep(i,,n){

         Dfs(,i,,<<i,c[i]);

         Dfs(,i,,<<i,b[i]);

         Dfs(,i,,<<i,a[i]);

     }

     printf("%d",ans);

 }

 int main(){

     Init();

     Work();

 }