购物 | 基础dp

题目描述：
中文

题目思路：

考虑前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
***/