题目描述:
中文

题目思路:

考虑前i个物品,满足连续能吃的情况下剩余k个,所需的最小费用。

答案即为dp[n][0]

接下来考虑dp状态转移

首先枚举第几天、然后今天要买多少个(0~m)

那么买的个数就可以由上一天转移过来

此时注意dp的条件:满足连续能吃

所以说假设枚举今天要买k个,昨天剩余j个,那么连续之后今天就剩余k+j-1个

所以:(temp是买的k个所需费用)
图片说明

Code:

ll n,m,p;
ll dp[505][505];///前i个剩余k个最小费用
ll a[505][505];
int main()
{
    read(n);read(m);
    for(int i=1;i<=n;i++){
        for(int k=1;k<=m;k++){
            read(a[i][k]);
        }
        sort(a[i]+1,a[i]+1+m);
    }
    for(int i=0;i<=n;i++){
        for(int k=0;k<=n;k++){
            dp[i][k] = INF;
        }
    }
    dp[0][0] = 0;
    for(int i=1;i<=n;i++){
        ll temp = 0;
        for(int k=0;k<=m;k++){///买几个
            temp += a[i][k];
            for(int j=0;j+k-1<=n;j++){///剩余几个
                if(j+k-1>=0)
                    dp[i][j+k-1] = min(dp[i][j+k-1],dp[i-1][j]+k*k+temp);
            }
        }
    }
    printf("%lld\n",dp[n][0]);
    return 0;
}
/***
5
5 4 5 3 2
1 2 1 1 1
***/