Codeforces Round #325 (Div. 2) F:(meet in the middle)

一看题就觉得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
");
    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
");
            else if(s[i]==2) printf("LW
");
            else printf("MW
");
        }
    }
    return 0;
}

Codeforces Round #325 (Div. 2) F:(meet in the middle)

相关推荐