(IOI) 2009 Day 1 p4 Raisins

https://contest.yandex.com/ioi/contest/1362/problems/D/

先做二維前綴和之後好好DP即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 51;

int a[N][N];
int pre[N][N];
int dp[N][N][N][N];

int cal(int x1,int y1,int x2,int y2)
{
    return pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1];
}

int solve(int x1,int y1,int x2,int y2)
{
    if (x1 == x2 && y1 == y2) return 0;
    if (dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];
    int &ret = dp[x1][y1][x2][y2];
    ret = 2147483647;
    int _ = cal(x1,y1,x2,y2);
    for (int i=x1;x2>i;i++)
    {
        ret = min(ret,_ + solve(x1,y1,i,y2) + solve(i+1,y1,x2,y2));
    }
    for (int j=y1;y2>j;j++)
    {
        ret = min(ret,_ + solve(x1,y1,x2,j) + solve(x1,j+1,x2,y2));
    }
    //cout << "x1 = " <<x1 << " , y1 = " <<y1 << " , x2 = " << x2 << " , y2 = " << y2 << " , ret = " << ret <<endl;
    return ret;
}

int main ()
{
    memset(dp,-1,sizeof(dp));
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++)
    {
        for (int j=1;m>=j;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for (int i=1;n>=i;i++)
    {
        for (int j=1;m>=j;j++)
        {
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];
        }
    }
    printf("%d\n",solve(1,1,n,m));
}