一看题就觉得3^25暴力肯定挂。但是并不能想出思路
就当学习了，代码基本copy菊苣的。
前半部分暴力搜，将搜到的状态存在map里，这里只保存b-a和c-b是为了匹配方便
后半部分也是暴力搜状态，找到的状态去map里查询（比如后半搜到5，6，去map里找-5，-6）
感觉map好慢。看来有时候得去学习一下手写哈希表了
至于状态的保存，一开始想把每个操作保存为一个三位二进制，发现2^75位好像会爆啊。。
看了菊苣的才知道可以保存2位就好（3个状态）
膜拜菊苣。果然我还太渣
有个坑是全0 的数据。所以把ans初始化为-INF
#include"cstdio" #include"queue" #include"cmath" #include"stack" #include"iostream" #include"algorithm" #include"cstring" #include"map" #include"queue" #include"vector" #define ll long long using namespace std; const int MAXN = 200050; const int MAXE = 400050; const int INF = 0x3f3f3f3f; map<pair<int,int>,pair<int,ll> >H; pair<int ,ll> ans; int n,s[30],l[30],m[30],w[30]; void dfs1(int a,int b,int c,int dep,ll s){//前半部分暴力 if(dep>=(n+1)/2+1){ pair<int,ll> t=H[pair<int,int>(a-b,b-c)]; if(t.second==0) H[pair<int,int>(a-b,b-c)]=pair<int,ll>(a,s); else H[pair<int,int>(a-b,b-c)]=max(t,pair<int,ll>(a,s));//比较first return; } dfs1(a+l[dep],b+m[dep],c,dep+1,s<<2|1); dfs1(a+l[dep],b,c+w[dep],dep+1,s<<2|2); dfs1(a,b+m[dep],c+w[dep],dep+1,s<<2|3); } void dfs2(int a,int b,int c,int dep,ll s){ if(dep>=n+1){ pair<int,ll> t=H[pair<int,int>(b-a,c-b)]; if(t.second==0) return ; ans=max(ans,pair<int,ll>(a+t.first,t.second<<(n-(n+1)/2<<1)|s)); return; } dfs2(a+l[dep],b+m[dep],c,dep+1,s<<2|1); dfs2(a+l[dep],b,c+w[dep],dep+1,s<<2|2); dfs2(a,b+m[dep],c+w[dep],dep+1,s<<2|3); } int main(){ ans.first=-INF; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&l[i],&m[i],&w[i]); dfs1(0,0,0,1,0); dfs2(0,0,0,(n+1)/2+1,0); if(ans.first==-INF) printf("Impossible\n"); else{ for(int i=0;i<n;i++){ s[i]=ans.second&3; ans.second>>=2; } for(int i=n-1;i>=0;i--){ if(s[i]==1) printf("LM\n"); else if(s[i]==2) printf("LW\n"); else printf("MW\n"); } } return 0; }
Codeforces Round #325 (Div. 2) F:(meet in the middle)
原文：http://www.cnblogs.com/luxiaoming/p/5068095.html