购物

做完今天的N1，然后发现这不是一样的题目吗？？？

题意

我们每天可以最多购买m个糖果，连续买 k 个需要额外支付 。保证每天吃一个糖，求买n个糖果的最少代价。

分析

我们定义dp[i][j]，表示前i天买了j颗糖的代价。

我们对 m 颗糖可以贪心一下，一定是买更便宜的糖。

然后枚举今天买几颗即可。

然后为了保证每天都有糖吃，第 i 天从 dp[i-1][i-1] 开始转移就行了。

具体看代码实现。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 410;
const int M = 1e9+7;
int n,m,k,ok;

int a[maxn];

int dp[maxn][maxn];

signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    mem(dp,inf);dp[0][0] = 0;
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 1; j <= m; j++) cin>>a[j];
        sort(a+1,a+1+m);
        for(int k = i-1; k <= n; k++)
        {   
            int sum = 0;
            for(int j = 0; j <= m; j++)
            {   
                sum += a[j];
                dp[i][k+j] = min(dp[i][k+j],dp[i-1][k]+sum+j*j);
            }
        }
    }
    cout<<dp[n][n]<<endl;
    return 0;
}