链接：https://ac.nowcoder.com/acm/contest/24213/1015
来源：牛客网

题目描述

在遥远的东方，有一家糖果专卖店。
这家糖果店将会在每天出售一些糖果，它每天都会生产出m个糖果，第i天的第j个糖果价格为C[i][j]元。
现在的你想要在接下来的n天去糖果店进行选购，你每天可以买多个糖果，也可以选择不买糖果，但是最多买m个。（因为最多只生产m个）买来糖果以后，你可以选择吃掉糖果或者留着之后再吃。糖果不会过期，你需要保证这n天中每天你都能吃到至少一个糖果。
这家店的老板看你经常去光顾这家店，感到非常生气。（因为他不能好好睡觉了）于是他会额外的要求你支付点钱。具体来说，你在某一天购买了 k 个糖果，那么你在这一天需要额外支付 k2 的费用。

那么问题来了，你最少需要多少钱才能达成自己的目的呢？

输入描述: 

第一行两个正整数n和m，分别表示天数以及糖果店每天生产的糖果数量。
接下来n行（第2行到第n+1行），每行m个正整数，第x+1行的第y个正整数表示第x天的第y个糖果的费用。

输出描述: 

输出只有一个正整数，表示你需要支付的最小费用。

题型：

动态规划--求最小值

思路：

还是老规矩
1.明确原问题：求买了n颗糖果的最小费用
2.明确子问题：求买了j颗糖果的最小费用-->求在第i天共买过的j颗糖果的费用（吃掉的不减去）
3.明确状态转移方程：设dp[i][j]为在第i天共买过的j颗糖果的费用（吃掉的不减去），那么可以知道，dp[i][j]为  它自身  和  上一天（即i-1天）买过的糖果+这一天购买的糖果+额外支付费用  的较小值
这里要明确两个问题：1.是否/如何选取糖果使得购买钱数减少；2.额外支付费用与这一天购买的糖果的表达与计算
先看第一个问题：可以把每天的糖果按费用升序排序，每次顺序购买糖果，即可减少费用
再看第二个问题：可以考虑对每天的糖果费用求前缀和sum[]，那么某一天购买的糖果费用即为sum[i]（不用减sum[j]，因为前面糖果费用最小，肯定是从第一个糖果开始选的）
解决了两个问题，最后整理一下状态转移方程
我们发现第i-1天拥有的糖果数量没有表示出来，所以设k为第i-1天买过的糖果数量，那么由于j为第i天买过的糖果数量，所以第i天的购买糖果费用就为sum[i][j-k]（这里j-k是在第i天购买的糖果数量），额外支付费用为(j-k)*(j-k);
所以最后的方程就为：dp[i][j]=min(dp[i][j],dp[i-1][k]+sum[i][j-k]+(j-k)*(j-k));
4.明确初始化与i,j,k范围：初始化dp[0][0]为0，其他格子全为INF(0x3f3f3f3f3f3f3f3f)，注意：至少要设n*n的格子为INF，而不是n*m
i,j,k范围：i：1~n;
j:i~min(n,i*m);//最多只可能买到n颗或者i*m颗（取两者最小值）
k:max(i-1,j-m)~min(n,min(j,(i-1)*m));//max(i-1,j-m)表示1.k为第i-1天买过的糖果数量，所以k>=i-1;同时如果第i-1天都不买的话相当于k+m=j，所以k+m>=j（因为第i-1天可能会买）-->k>=j-m-->k=max(i-1,j-m)
这里k可能不是从i-1开始的，所以一楼大佬的代码似乎有些问题，但是数据测试点能过，可能数据有点弱了

代码： 

#include<bits/stdc++.h>
#define ll long long int
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
ll dp[320][320],a[320][320];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%lld",&a[i][j]);
		}
		sort(a[i]+1,a[i]+m+1);
		for(int j=1;j<=m;j++){
			a[i][j]+=a[i][j-1]; //求前缀和
		}
	}
	for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=999999999999; //初始化
        }
    }
	dp[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=min(n,i*m);j++){
			for(int k=max(j-m,i-1);k<=min(n,min((i-1)*m,j));k++){ //注意k的范围！
				dp[i][j]=min(dp[i][j],dp[i-1][k]+a[i][j-k]+(j-k)*(j-k));
			}
		}
	}
	printf("%lld\n",dp[n][n]); //注意答案是dp[n][n]!
	return 0;
}