这次学校网络赛还是挺不错的，有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
****************************************************************/