TIOJ 1449 郵局設置問題EXTREME

四邊型不等式 OwO~~

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int dp[1011][1011] = {0};
int rg[1011][1011] = {0};
int val[1011] = {0};
int w[1011][1011] = {0};
int main()
{
    int n, k; scanf("%d %d", &n, &k);
    for(int lx = 2;lx <= n;lx++)
        scanf("%d", val+lx);
    if(n <= k){puts("0"); return 0;}
    sort(val+1, val+n+1);
    for(int lx = 1;lx <= n;lx++)
        for(int ly = lx+1;ly <= n;ly++)
            w[lx][ly] = w[lx][ly-1] + val[ly] - val[(lx+ly)/2];
    
    for(int lx = 1;lx <= n;lx++)
        dp[lx][lx] = 0, rg[lx][lx] = lx-1,
        dp[lx][1] = w[1][lx], rg[lx][1] = 0;
    
    for(int lc = 2;lc <= n;lc++){
        for(int ll = 1;ll <= n-lc;ll++){
            int x = lc+ll, y = ll+1;
            int min_i = rg[x-1][y];
            int min_val = dp[min_i][y-1] + w[min_i+1][x];
            for(int i = rg[x-1][y];i <= rg[x][y+1] and i >= y-1;i++){
                int get_val = dp[i][y-1] + w[i+1][x]; 
                if(min_val > get_val)
                    min_val = get_val,
                    min_i = i;
            }
            rg[x][y] = min_i;
            dp[x][y] = min_val;
        }
    }
    printf("%d\n", dp[n][k]);
    return 0;
}