写了两个小时的说，思路和状态转移方程不难想，但是代码调试了好久。刚开始想用三维dp，后来发现自己把自己绕进去了，二维足够(滚动数组应该也可以进一步优化到一维。）

考查：贪心，前缀和，线性dp

状态表示：dp[i][j] 表示第i天，手里有j个糖果时花费的最少费用，因为每天至少吃一个，贪心的想法，每天就吃一个，所以j大于等于1，答案即为dp[n][1]。

转移方程：设第i天买了k个糖果，则


dp[i][j]=min(dp[i][j],dp[i-1][j-k+1]+val[i][k]+k*k);

就是把第i天拥有的j个糖果分成两部分，一部分来自k，另一部分来自i-1天剩下的，所以是j-k+1。

需要注意的是第i-1天可能不能贡献j-k+1个，因为前一天有的最多糖果数比i天少，在这种情况下说明第i天买k个太少了，继续枚举就好，当前新买的糖果要花费的价格可以用前缀和提前处理好，再加上k的平方就好。

上代码。


#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&-x)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
ll val[301][301]={0};
ll dp[301][90001]={0};
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cin>>val[i][j];
    }
    for(int i=1;i<=n;i++) sort(val[i]+1,val[i]+m+1);//优先买价格低的。
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) val[i][j]=val[i][j-1]+val[i][j];//前缀和
    }
    for(int i=1;i<=m;i++) dp[1][i]=val[1][i]+i*i;//初始化
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i*m-(i-1)&&j<=n-i+1;j++){//i*m-(i-1)是第i天最多拥有多少糖果，n-i+1是满足条件的最大的j值。
            int w=(i-1)*m-(i-2);//i-1天最多有w个糖果
            dp[i][j]=1e10;
            for(int k=0;k<=j;k++){
                if(j-k+1<=w){
                    dp[i][j]=min(dp[i][j],dp[i-1][j-k+1]+val[i][k]+k*k);
                }
                else{
                    continue;//j-k+1大于w时，说明前一天不能贡献了，需要今天多买一点，所以让k增加。
                }
            }
        }
    }
    cout<<dp[n][1];
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}