---
tags: IOI
---
# IOI2009 Day1-4 レーズン (Raisins)

## 問題

https://www.ioi-jp.org/ioi/2009/problems/day1/Raisins_jp.pdf
https://oj.uz/problem/view/IOI09_raisins

$N \times M$ マスのチョコレートがあり、各マスには $R_{i,j}$ 個のレーズンが入っています。
あなたは以下の操作を繰り返してこのチョコレートを $N \times M$ 個に分割したいです。

- チョコレートを1つ選び、縦か横にマスにそって切る。これにはそのチョコレートに入っているレーズンの個数分のコストがかかる。

コストの合計の最小値を求めてください。

$N, M ≤ 50$

## 考察

レーズンが連続的ならレーズンが半分になるように切るのが最適(？)

DPを考えると、これは蟻本にもある区間DP

## 実装

https://oj.uz/submission/221234

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned;
#define name3(a,b,c,d,...) d
#define rep1(b) for(int i = 0; i < b; i++)
#define rep2(i,b) for(int i = 0; i < b; i++)
#define rep3(i,a,b) for(int i = a; i < b; i++)
#define rep(...) name3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }


int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    uint a[51][51] = {};
    rep(n) rep(j, m) cin >> a[i + 1][j + 1];
    rep(n + 1) rep(j, m) a[i][j + 1] += a[i][j];
    rep(j, m + 1) rep(n) a[i + 1][j] += a[i][j];
    static uint dp[50][50][51][51];
    memset(dp, 0xff, sizeof(dp));
    rep(50) rep(j, 50) dp[i][j][i + 1][j + 1] = 0;
    rep(x, 1, n + 1) rep(y, 1, m + 1) if(x != 1 || y != 1){
        rep(x1, n - x + 1){
            int x2 = x1 + x;
            rep(y1, m - y + 1){
                int y2 = y1 + y;
                rep(x3, x1 + 1, x2) chmin(dp[x1][y1][x2][y2], dp[x1][y1][x3][y2] + dp[x3][y1][x2][y2]);
                rep(y3, y1 + 1, y2) chmin(dp[x1][y1][x2][y2], dp[x1][y1][x2][y3] + dp[x1][y3][x2][y2]);
                dp[x1][y1][x2][y2] += a[x2][y2] + a[x1][y1] - a[x1][y2] - a[x2][y1];
            }
        }
    }
    cout << dp[0][0][n][m] << endl;
}