100722E The Bookcase

题目大意

给你一些书的高度和宽度，有一个一列三行书柜，要求放进去书后，三行书柜的高的和乘以书柜的宽度最小。问这个值最小是多少。

分析

我们可以先将所有书按照高度降序排好，这样对于每一层只要放过书高度边不会改变。我们设第一本书放在第一层，用dp[i][j][k]表示考虑到第i个，第二层的厚度为j，第三层的厚度为k的情况时书架的最小总高度是多少，如果j或k是0则代表这一层以前没放过书，然后根据这个转移就行了。由于空间不够我们使用滚动数组。注意由于至少有三本书，所以每一层至少会放一个（这样可以使答案更优）。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define gmin(x,y) x=min(x,y)

const int inf = 0x3f3f3f3f;

struct node {

      int h,w;

};

node d[];

int dp[][][],maxw[];

inline bool cmp(const node x,const node y){return x.h>y.h;}

int main(){

      int n,m,i,j,k,t;

      scanf("%d",&t);

      while(t--){

          memset(maxw,,sizeof(maxw));

          scanf("%d",&n);

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

          scanf("%d%d",&d[i].h,&d[i].w);

        }

        sort(d+,d+n+,cmp);

        maxw[]=d[].w;

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

          maxw[i]=maxw[i-]+d[i].w;

        int now=;

        memset(dp[now],0x3f,sizeof(dp[now]));

        dp[now][][]=d[].h;

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

          now^=;

          memset(dp[now],0x3f,sizeof(dp[now]));

          for(j=;j<=maxw[i-];j++)

            for(k=;k+j<=maxw[i-];k++)

              if(dp[now^][j][k]<inf){

                gmin(dp[now][j][k],dp[now^][j][k]);

                if(!j)gmin(dp[now][j+d[i].w][k],dp[now^][j][k]+d[i].h);

                  else gmin(dp[now][j+d[i].w][k],dp[now^][j][k]);

                if(!k)gmin(dp[now][j][k+d[i].w],dp[now^][j][k]+d[i].h);

                  else gmin(dp[now][j][k+d[i].w],dp[now^][j][k]);

              }

        }

        int ans=inf;

        for(i=;i<=maxw[n];i++)

          for(j=;j+i<=maxw[n];j++){

              k=maxw[n]-i-j+d[].w;

              if(dp[now][i][j]<inf)

              gmin(ans,(dp[now][i][j])*max(i,max(j,k)));

          }

        printf("%d\n",ans);

      }

      return ;

}

巴特西

100722E The Bookcase

最新文章

热门文章