购物

题意：
有一家糖果店，每天可以生产m颗糖果，你在接下来n天会去买糖果，你每天必须吃一颗糖果，你买的糖果可以保存以后吃，你每天买糖果还需要额外花当天买的糖果个数的平方的钱，求这n天你最少花多少钱？

思路：
dp
dp[i][j]表示前i天买j颗糖果的最少花费。
sum[i][o]表示第i天买o颗糖果的糖果花费。
前i天买的糖果为第i天买的糖果加上前i-1买的糖果，注意每天必须吃一颗糖果（既i<=j）。
状态转移方程：
dp[i][j]=min(dp[i-1][j-o]+o*o+sum[i][o]) (j>=i&&j-o>=i-1&&o>=0&&o<=m);(o为第i天买的糖果数)

代码：

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int inf=1000000007;

ll d[305][305];
ll sum[305][305], dp[305][305];

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",&d[i][j]);
        }
        sort(d[i]+1,d[i]+m+1);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            sum[i][j]=sum[i][j-1]+d[i][j];
        }
    }
    fill(dp[0],dp[0]+305*305,inf);
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            dp[i][j]=dp[i-1][j];
            for(int o=1;o<=m;o++)
            {
                if(j>=o&&j-o>=i-1)
                dp[i][j]=min(dp[i][j],dp[i-1][j-o]+sum[i][o]+o*o);
            }
        }
    }
    cout << dp[n][n] << endl;
    return 0;
}