[动态规划][状压DP][剪枝搜索] XDOJ 1420 2019西电acm校赛网络赛J题 垒箱子

题目链接

这次学校网络赛还是挺不错的,有3道题(F I J)都是值得一做的emm,J题胡乱暴力+dp拿了个一血,I题胡乱暴力也过了

当然由于我FFT/NTT&斯特林数学的不行所以F题并不会做,虽然推出来公式和dalao一样但是没法把复杂度降下去,等到学会了应该会放个F的题解

J题吧,跟UVa 437 The Tower of Babylon很像,当然只是看上去很像,UVa 437的限制是每种箱子必须叠在比他严格小的另一个上,然后箱子无限用,XDOJ 1420 是叠在长宽大于等于该箱子的另一个箱子上,但是每种箱子只能用一次。
如果箱子的数量少一点的话,其实完全可以直接完全状态压缩动态规划,但是这题数量是30,压缩成二进制的话2^30肯定会超时,所以需要一点操作。。

首先先全部暴搜,dfs(x,S)表示当前以箱子x号为最底部箱子,之前已经用过的也就是还在x更底下的箱子情况为S(S是一个十进制数,展开成01二进制串表示30个箱子是否被使用过)所能达到的最高的高度,每次都打一遍结果,很快可以发现,当取到某一个箱子之后,在某些情况下他后面的搜索路径就是固定的。

就比如说 某次搜到了箱子3,然后他之后的搜索路径就只能放箱子6和7,然后把每次搜索路径都打出来就会发现,其实之后的每次搜到3都会是走6和7,除非6和7之前已经被用过了也就是说6或7变成了3底下的箱子,这时候后面的路径会发生一些变化,因为每个箱子只能用一次。(这里本该举一组样例但我实在找不到当时画的样例了emm)

然后到这里就可以想一下是不是可以用这个特性对dfs(x,S)进行剪枝和记忆化搜索,首先把S的定义反转,让S这个二进制数表示尚未使用过的箱子”的情况,比如00101表示1号和3号箱子还没有被用过,245号箱子已经被用过了。这样的话,每次dfs的时候可以记录下来一个dp(x,TS)的记忆化结果,其中TS是S和“理论上可以放到x上的所有箱子的集合”KS相与的结果,这里后者可以n^2复杂度枚举预处理,我的代码里是存储到ky[x]的数组里。这样的话,每次dfs就是先把TS求出来,然后判断(x,TS)这个对有没有在之前被搜索过,如果有的话就直接返回结果,这里的这个结果可以用一个map<pair<int,int>, int> 来保存,如果没有出现过的话的话就直接暴搜,这样的话每种箱子作为底的每种情况只会被搜到一次,就等于提前把绝不可能走到的箱子和已经走过的路径都剪掉了。把所有的状况想象成图的话,每个箱子三种形态那就是有90个节点,每个结点出发能走的最长的路径最多30个,如果能保证每种情况只走一次其实是相当快的(主要是我并不会严格证明复杂度emmm)


代码如下,不过我的代码之前写错了多考虑了“当前箱子的上一个箱子”,后来直接改了dfs,所以会有一个诡异的二重循环和诡异的dfs三个参数,其实根本没必要二重循环,dfs的参数也只需要一个idx和一个S就可以了。

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const int maxn=1e3+5;
 
int ed[35][3],n;
int fd[95][3];
int pos[95];
int ky[95];
vector<int> G[95];
 
int flen[95];
int ans;
 
int mc=0;
map<pair<int,int>,int >mp;
int vis[95][95];
 
int dfs(int idx,int idy,int S){
    mc=max(mc,cnt);
    int TS= (S&ky[idy]);
    if(mp[make_pair(idy,TS)]!=0) return mp[make_pair(idy,TS)];
    int tmp=0,res=0;
    for(int i=0;i<flen[idy];i++){
        tmp=G[idy][i];
        if((S>>(pos[tmp]))&1)
            res=max(res,dfs(idy,tmp,S^(1<<(pos[tmp]))));
    }
    return mp[make_pair(idy,TS)]=res+fd[idy][2];
}
 
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&ed[i][0],&ed[i][1],&ed[i][2]);
        sort(ed[i],ed[i]+3);
        ans=max(ans,ed[i][2]);
        fd[3*(i-1)][0]=ed[i][0],fd[3*(i-1)][1]=ed[i][1],fd[3*(i-1)][2]=ed[i][2];
        fd[3*(i-1)+1][0]=ed[i][1],fd[3*(i-1)+1][1]=ed[i][2],fd[3*(i-1)+1][2]=ed[i][0];
        fd[3*(i-1)+2][0]=ed[i][0],fd[3*(i-1)+2][1]=ed[i][2],fd[3*(i-1)+2][2]=ed[i][1];
    }
    for(int i=0;i<3*n;i++)
        pos[i]=i/3;
    for(int i=0;i<3*n;i++){
        for(int j=0;j<3*n;j++){
            if(pos[i]!=pos[j]&&fd[i][0]>=fd[j][0]&&fd[i][1]>=fd[j][1])
                G[i].push_back(j),ky[i]|=(1<<(pos[j]));
        }
    }
 
    for(int i=0;i<3*n;i++)
        flen[i]=G[i].size();
         
    for(int i=0;i<3*n;i++){
        for(int j=0;j<flen[i];j++){
            ans=max(ans,fd[i][2]+dfs(i,G[i][j], ((1<<n)-1) - (1<<(pos[i])|(1<<pos[G[i][j]]))));
        }
    }
    printf("%d",ans);
    return 0;
}
/**************************************************************
    Problem: 1420
    Language: C++
    Result: 正确
    Time:23 ms
    Memory:1764 kb
****************************************************************/

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据