JOI 2012 春合宿 JOI Flag(日本情報オリンピック旗) 難易度8

普通にdfsをすると、TLEする

高速化をする：
N<=1000、つまり埋まっている文字の場所は高々1000個　これはかなりスカスカ
ある区画を見ているときに、その区画に文字が無いことがわかっているなら、明らかにその区画はコスト0であるので、その時点で0を返してしまって良い

signed main(){

    cin.tie(0);
    ios::sync_with_stdio(0);

    int K,N;cin >> K >> N;
    vector<vector<P>>vec(3);
    rep(i,N){
        int x,y;char C;cin >> x >> y >> C;
        x--;y--;
        int c = C=='J'?0:(C=='O'?1:2);
        vec[c].push_back({x,y});
    }

    auto fillcost = [&](PP pq,char C)->int {
        int c = C=='J'?0:(C=='O'?1:2);

        auto [p,q] = pq;
        auto [il,ir] = p;
        auto [jl,jr] = q;
        //il<=i<ir,jl<=j<jrで、cと一致しないものの個数
        int cnt = 0;
        rep(ci,3)if(ci!=c){
            for(auto [x,y]:vec[ci]){
                if(il<=x&&x<ir&&jl<=y&&y<jr)cnt++;
            }
        }
        return cnt;

    };

    map<PP,int>mp;
    auto dfs = [&](auto dfs,PP pq)->int {
        if(mp.count(pq))return mp[pq];
        auto [p,q] = pq;
        auto [il,ir] = p;
        auto [jl,jr] = q;
        //コストを返す
        if(ir-il==1){return 0;}
        bool emp = true;
        rep(c,3){
            for(auto [i,j]:vec[c]){
                if(il<=i&&i<ir&&jl<=j&&j<jr){emp = false;break;}
            }
            if(emp==false)break;
        }
        if(emp)return mp[pq] = 0;
        //ぜんぶJ、ぜんぶO、ぜんぶI、一つレベルの低いものの置き方を全部ためす
        int mdi = (il+ir)/2,mdj = (jl+jr)/2;
        vector<PP>IJ = {
            {{il,mdi},{jl,mdj}},
            {{il,mdi},{mdj,jr}},
            {{mdi,ir},{jl,mdj}},
            {{mdi,ir},{mdj,jr}}
        };
        string S = "JOI_";
        sort(all(S));
        int res = INF;
        do{
            int tmp = 0;
            rep(k,4){
                if('A'<=S[k]&&S[k]<='Z')tmp += fillcost(IJ[k],S[k]);
                else tmp+=dfs(dfs,IJ[k]);
            }
            chmin(res,tmp);
        }while(next_permutation(all(S)));
        return mp[pq] = res;

    };
    cout << dfs(dfs,{{0,(1<<K)},{0,(1<<K)}}) << endl;;


}