题目大意

有 天，每天可购买 个糖，不同时间、不同的糖有不同价格。每天购买 个糖有额外代价 。须保证第 天结束时累计购买数达到 。问最小代价。

题解

写了一个朴素的二维 DP，预先对每一天的糖价格排序，然后设 为第 天结束时买了 个糖的最小代价。则

其中 表示前 天最小的 个糖的价格和。

这么做是 的。当然由于后面整个都是只和 相关的函数，因此应该也可以用单调队列维护，时间复杂度降为 。

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, c[305][305], sum[305][305];
int f[305][305];
inline int sqr(int x){
    return x * x;
}
void init(){
    n = read(), m = read();
    REP(i, 1, n){
        REP(j, 1, m)
            c[i][j] = read();
        sort(c[i] + 1, c[i] + m + 1);
        sum[i][0] = 0;
        REP(j, 1, m)
            sum[i][j] = sum[i][j - 1] + c[i][j];
    }
}
void solve(){
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    REP(i, 1, n)
        REP(j, i, n)
            REP(k, max(i - 1, j - m), j)
                f[i][j] = min(f[i][j], f[i - 1][k] + sqr(j - k) + sum[i][j - k]);
    printf("%d\n", f[n][n]);    
}
int main(){
    init();
    solve();
    return 0;
}