購物

思路

最優值問題，我們考慮$dp$，$dp[i][j]$表示前$i$天已經購買了$j$個糖果的花費最小值，顯然$dp[i][j]$可以從$dp[i?1][k]$轉移過來，具體轉移過程看代碼注釋部分吧。

對于答案我們顯然是在第$n$天剛好購買了$n$個糖果，這樣是最優的，對于每一天購買糖果，我們一定是優先選擇花費更小的，這樣才能保證最優值.

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h>#define mp make_pair #define pb push_back #define endl '\n' #define mid (l + r >> 1) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define ls rt << 1 #define rs rt << 1 | 1using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N = 310;ll a[N][N], n, m, dp[N][N];int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read(), m = read();for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {a[i][j] = read();}sort(a[i] + 1, a[i] + 1 + m);//對糖果價錢排個序for(int j = 1; j <= m; j++) {//求個前綴和方便后面的dp。a[i][j] += a[i][j - 1];}}memset(dp, 0x3f, sizeof dp);dp[0][0] = 0;for(int i = 1; i <= n; i++) {//按照套路兩重循環i, j分別代表天數跟糖果總數。for(int j = i; j <= min(n, i * m); j++) {//因為每一天一定要有糖果，所以一定是第i天最少要有i個糖果。//當天獲得的最大糖果數量是min(n, i * m)，這個一定要保證，因為最多只要n個，當天最多只能得到i * m個for(int k = i - 1; k <= min(n, (i - 1) * m) && k <= j; k++) {//前一天轉移過來的最少也要有i - 1個糖果，//這里考慮轉換的時同樣的要考慮上一步轉移過來的是否符合要求，所以規定數量//k <= j && k <= 前幾天糖果數量總和 && k <= n 我們需要的最多糖果。dp[i][j] = min(dp[i][j], dp[i - 1][k] + a[i][j - k] + (j - k) * (j - k));}}}cout << dp[n][n] << endl;return 0; }

總結

以上是生活随笔為你收集整理的购物（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。