每日一题 8月4日购物 有限制的DP

题目链接：https://ac.nowcoder.com/acm/problem/14526
题目大意：


思路：
我们预处理每天买i个的最小费用，然后直接分组DP就可以了。有个限制：第i天至少买i个。因为每天至少吃一个。

#pragma GCC optimize(3, "Ofast", "inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define rint register int
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char buf[1<<20],*p1=buf,*p2=buf;
inline int read() {
    int f=0,fu=1;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')
            fu=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        f=(f<<3)+(f<<1)+c-48;
        c=getchar();
    }
    return f*fu;
}

inline void print(LL x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x >= 10)
        print(x / 10);
    putchar(x % 10 + '0');
}

vector<int> v[305];
vector<pair<int, int> > a[305];
int f[305][305];
int main() {

    int n=read(), m=read();
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            int x=read();
            v[i].push_back(x);
        }
        sort(v[i].begin(), v[i].end());
        int w=0;
        for(int j=0; j<m; j++){
            w+=v[i][j];
            a[i].push_back({j+1, (w+(j+1)*(j+1))});
            //cout<<i<<" "<<j+1<<" "<<(w+(j+1)*(j+1))<<endl;
        }
    }

    memset(f, 0x3f, sizeof(f));
    f[0][0]=0;
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            for(int k=0; k<a[i].size(); k++){
                int v=a[i][k].first, w=a[i][k].second;
                f[i][j]=min(f[i][j], f[i-1][j]);
                if(j>=v){
                    f[i][j]=min(f[i][j], f[i-1][j-v]+w);
                }
            }
        }
    }
    printf("%d\n", f[n][n]);

    return 0;
}