四川星星建设集团有限公司网站,建网站自学,申请公司邮箱,制作app开发制作购物
思路
最优值问题#xff0c;我们考虑dpdpdp#xff0c;dp[i][j]dp[i][j]dp[i][j]表示前iii天已经购买了jjj个糖果的花费最小值#xff0c;显然dp[i][j]dp[i][j]dp[i][j]可以从dp[i−1][k]dp[i - 1][k]dp[i−1][k]转移过来#xff0c;具体转移过程看代码注释部分吧。…购物
思路
最优值问题我们考虑dpdpdpdp[i][j]dp[i][j]dp[i][j]表示前iii天已经购买了jjj个糖果的花费最小值显然dp[i][j]dp[i][j]dp[i][j]可以从dp[i−1][k]dp[i - 1][k]dp[i−1][k]转移过来具体转移过程看代码注释部分吧。
对于答案我们显然是在第nnn天刚好购买了nnn个糖果这样是最优的对于每一天购买糖果我们一定是优先选择花费更小的这样才能保证最优值.
代码
/*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 pairint, 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;
}
