一眼题...这个数据范围也太明显了吧...
suma1==suma2 && sumb1==sumb2 && sumc1==sumc2
相当于suma1-sumb1==sumb2-suma2 && suma1-sumc1==sumc2-suma2
于是前一半O(3^(N/2))搜出所有情况的suma1-sumb1和suma1-sumc1，后一半搜出sumb2-suma2和sumc2-suma2，都丢到一个数组里作为两个关键字排序，在两个关键字都相同的一段里面找到前一半最大的suma和后一半最大的suma，更新答案即可
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> using namespace std; const int maxn=4000010, inf=1e9+1; struct poi{int x, y, st, a, ty;}v[maxn]; int n, cnt, ans, ansst1, ansst2; int a[maxn], b[maxn], c[maxn], mi[110]; void read(int &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } inline bool cmp(poi a, poi b){return a.x==b.x?(a.y<b.y):a.x<b.x;} inline void printans(int x, int num) { for(int i=1;i<=num;i++) { int now=x%3; if(now==0) printf("LM "); else if(now==1) printf("LW "); else printf("MW "); x/=3; } } int main() { read(n); for(int i=1;i<=n;i++) read(a[i]), read(b[i]), read(c[i]); int l=(n+1)>>1, r=n; mi[0]=1; for(int i=1;i<=l;i++) mi[i]=mi[i-1]*3; for(int i=0;i<=mi[l]-1;i++) { int tmpa=0, tmpb=0, tmpc=0; for(int j=1;j<=l;j++) { int tmp=i/mi[j-1]%3; if(tmp==0) tmpa+=a[j], tmpb+=b[j]; else if(tmp==1) tmpa+=a[j], tmpc+=c[j]; else tmpb+=b[j], tmpc+=c[j]; } v[++cnt].x=tmpa-tmpb; v[cnt].y=tmpa-tmpc; v[cnt].a=tmpa; v[cnt].st=i; v[cnt].ty=1; } for(int i=0;i<=mi[r-l]-1;i++) { int tmpa=0, tmpb=0, tmpc=0; for(int j=1;j<=r-l;j++) { int tmp=i/mi[j-1]%3; if(tmp==0) tmpa+=a[j+l], tmpb+=b[j+l]; else if(tmp==1) tmpa+=a[j+l], tmpc+=c[j+l]; else tmpb+=b[j+l], tmpc+=c[j+l]; } v[++cnt].x=tmpb-tmpa; v[cnt].y=tmpc-tmpa; v[cnt].a=tmpa; v[cnt].ty=2; v[cnt].st=i; } sort(v+1, v+1+cnt, cmp); ans=-inf; for(int i=1, j=1;i<=cnt;i=j) { int tmp1=-inf, tmp2=-inf, tmpst1=0, tmpst2=0; while(v[j].x==v[i].x && v[j].y==v[i].y) { if(v[j].ty==1) {if(tmp1<v[j].a) tmp1=v[j].a, tmpst1=v[j].st;} else {if(tmp2<v[j].a) tmp2=v[j].a, tmpst2=v[j].st;} j++; } if(tmp1==-inf || tmp2==-inf) continue; if(tmp1+tmp2>ans) ans=tmp1+tmp2, ansst1=tmpst1, ansst2=tmpst2; } if(ans==-inf) return puts("Impossible"), 0; printans(ansst1, l); printans(ansst2, r-l); }