DP Optimization another kind, C++ (gcc)

DP Optimization another kind

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

int n, m, a[4001][4001], dp[801][4001], opt[801][4001], cost[4001][4001];

inline int query(int from, int to){
    int r1 = from, c1 = from, r2 = to, c2 = to;
    return (a[r2][c2] - a[r1-1][c2] - a[r2][c1-1] + a[r1-1][c1-1])/2;
}

void build(){
    for(int j = 1; j <= n; j++){
        for(int k = 1; k <= m; k++)
            a[j][k] += a[j][k-1];
    }
    
    for(int k = 1; k <= m; k++){
        for(int j = 1; j <= n; j++)
            a[j][k] += a[j-1][k]; 
    }
    
    for(int j = 1; j <= n; j++)
        for(int k = j; k <= m; k++)
            cost[j][k] = query(j, k);
}

void foo(int gon, int l, int r, int optl, int optr){
    if(l > r) return;
    if(l == r){
        int &ans = dp[gon][l];
        int &ind = opt[gon][l];
        ans = 1e9, ind = -1;
        for(int j = optl; j <= optr; j++)
            if(ans > (dp[gon-1][j-1] + cost[j][l])){
                ans = dp[gon-1][j-1] + cost[j][l];
                ind = j;
            }
        return;
    }
    int m = (l+r) >> 1;
    foo(gon, m, m, optl, optr);
    foo(gon, l, m-1, optl, opt[gon][m]);
    foo(gon, m+1, r, opt[gon][m], optr);
}

int solve(int gon){
    for(int j = 1; j <= n; j++)
        dp[1][j] = cost[1][j];
    for(int j = 2; j <= gon; j++)
        foo(j, 1, n, 1, n);
    return dp[gon][n];
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    memset(a, 0, sizeof(a));
    memset(dp, 1e9, sizeof(dp));
    
    int gon;
    scanf("%d%d\n",&n ,&gon);
    m = n;// = 4000;
    //gon = 10;
    for(int j = 1; j <= n; j++){
        char buffer[8001];
        gets(buffer);
        for(int k = 1; k <= m; k++)
            a[j][k] = buffer[2*(k - 1)] - '0';
    }
    build();
    cout << solve(gon) << endl;
    return 0;
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development