ABC 008 D

今回はこの問題です。

abc008.contest.atcoder.jp

問題文はめどいので省略します…単純な話ですが文章で説明するのは大変です。

この問題のやっかいなところは、wやhが10^6まで大きくなることです。メモ化するにも工夫が要ります。
今回はmapを使いました。キーは左下の座標、右上の座標の4つの数字になっています。pairがいっぱい出てくるので見にくいしちょっと汚い気がします…。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    int w, h, n;
    vector<int> goldx, goldy;
    map<pair<pair<int, int>, pair<int, int> > , long long int> result;
     
    bool isin(int x1, int y1, int x2, int y2, int nowx, int nowy)
    {
        return (nowx >= x1 && nowx <= x2 && nowy >= y1 && nowy <= y2);
    }
     
    long long int solve(int x1, int y1, int x2, int y2)
    {
        // cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
        if(!isin(1, 1, w, h, x1, y1) || !isin(1, 1, w, h, x2, y2)) return 0;
        if(result.find(make_pair(make_pair(x1, y1), make_pair(x2, y2))) != result.end()) return result[make_pair(make_pair(x1, y1), make_pair(x2, y2))];
        long long int ans = 0;
        for(int i = 0; i < n; i++){
            int nowx = goldx[i], nowy = goldy[i];
            if(!isin(x1, y1, x2, y2, nowx, nowy)) continue;
            long long int result = (x2 - x1) + (y2 - y1) + 1;
            if(nowx - 1 >= x1 && nowy - 1 >= y1) result += solve(x1, y1, nowx - 1, nowy - 1);
            if(nowx + 1 <= x2 && nowy - 1 >= y1) result += solve(nowx + 1, y1, x2, nowy - 1);
            if(nowx - 1 >= x1 && nowy + 1 <= y2) result += solve(x1, nowy + 1, nowx - 1, y2);
            if(nowx + 1 <= x2 && nowy + 1 <= y2) result += solve(nowx + 1, nowy + 1, x2, y2);
            ans = max(ans, result);
        }
        // cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << ans << endl;
        result[make_pair(make_pair(x1, y1), make_pair(x2, y2))] = ans;
        return ans;
    }
     
    int main()
    {   
        cin >> w >> h >> n;
        for(int i = 0; i < n; i++){
            int tmpx, tmpy;
            cin >> tmpx >> tmpy;
            goldx.push_back(tmpx);
            goldy.push_back(tmpy);
        }
        cout << solve(1, 1, w, h) << endl;
    }

メモ化再帰で、引数で指定された範囲で得られる金塊の数の最大値を求めていきます。resultにはその結果が書き込まれています。
まず、動かす装置を選びます。そのあと、その装置の上下左右の範囲について、得ることのできる金塊の数の最大値を求めます。その結果と、最初に選んだ装置を動かすことで得られる金塊の数の和を求めます。範囲内にある装置すべてに対して求め、その最大値を選んでresultに記録すればいいです。