[NC14526] 购物

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

在遥远的东方，有一家糖果专卖店。

这家糖果店将会在每天出售一些糖果，它每天都会生产出$m$个糖果，第i天的第j个糖果价格为$C[i][j]$元。

现在的你想要在接下来的n天去糖果店进行选购，你每天可以买多个糖果，也可以选择不买糖果，但是最多买$m$个。（因为最多只生产$m$个）买来糖果以后，你可以选择吃掉糖果或者留着之后再吃。糖果不会过期，你需要保证这$n$天中每天你都能吃到至少一个糖果。

这家店的老板看你经常去光顾这家店，感到非常生气。（因为他不能好好睡觉了）于是他会额外的要求你支付点钱。具体来说，你在某一天购买了 $k$ 个糖果，那么你在这一天需要额外支付 $k^2$ 的费用。

那么问题来了，你最少需要多少钱才能达成自己的目的呢？

输入描述:

1
2
第一行两个正整数n和m，分别表示天数以及糖果店每天生产的糖果数量。
接下来n行（第2行到第n+1行），每行m个正整数，第x+1行的第y个正整数表示第x天的第y个糖果的费用。

输出描述:

1
输出只有一个正整数，表示你需要支付的最小费用。

示例1

输入

1
2
3
4
3 2 
1 1
100 100 
10000 10000

输出

1
107

示例2

输入

1
2
3
4
5
6
5 5
1 2 3 4 5
2 3 4 5 1 
3 4 5 1 2 
4 5 1 2 3 
5 1 2 3 4

输出

1
10

备注

1
对于100%的数据，1 ≤ n, m ≤ 300 , 所有输入的数均 ≤ 1e6。

题解

题目解析

卡了我好长时间,一直没有分辨出来是哪种类型,最后发现是一个背包题.

我实在是懒得写这个题的题解了,我这里引用别人的题解:「线性DP」购物_小灵不想卷的博客

这道题的状态转移方程为:

1
2
3
4
5
解释一下:
i:第i天
j:买了j个糖果
k:一个标记,dp[i-1][k]表示i-1天买了k个糖
j-k:因为一共要买j个糖果,i-1天买了k个,所以今天要买j-k个,最终买了j个.
1
2
3
4
5
6
7
8
9
10
i = 1, j = 1;
  k = 0, dp[1][1] = dp[0][0] + arr[1][1] + 1^2; // 0+1+1 第0天买了0个,第1天买了1个.
  k = 1, dp[1][1] = dp[0][1] + arr[1][0] + 0^2; // INF+0+0 第0天买了1个,第1天买了0个.
i = 1, j = 2;
  k = 0, dp[1][2] = dp[0][0] + arr[1][2] + 2^2; // 0+2+4 第0天买了0个,第1天买了2个.
  k = 1, dp[1][2] = dp[0][1] + arr[1][1] + 1^2; // INF+2+2 第0天买了1个,第1天买了1个.
  k = 2, dp[1][2] = dp[0][2] + arr[1][0] + 0^2; // INF+0+0 第0天买了2个,第1天买了0个.
i = 2, j = 2;
  // ...
// 以此类推...

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 310;

int sum[MAXN][MAXN],dp[MAXN][MAXN];

int main(){
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			cin >> sum[i][j];
		sort(sum[i]+1,sum[i]+m+1);//将第i天的从小到大排一遍,因为我们必须从小往大买
		for(int j=1;j<=m;j++)
			sum[i][j] += sum[i][j-1];//前缀和
	}

	memset(dp,0x3f3f3f3f,sizeof(dp));
	dp[0][0] = 0;
	for(int i=1;i<=n;i++){
        //为什么是min(i*m,n),是因为第一行只有m个,如果m<n的话,会炸的.min(i*m,n)的最差情况是把前i行都买了还不到n个.
		for(int j=i;j<=min(i*m,n);j++){
            //第i天最少买j-j(0)个[前面都买齐了],最多买j-(i-1)个[也就是前面每天只买一个,第i天把没满j的剩下的全买了].
			for(int k=i-1;k<=j;k++){
				dp[i][j] = min(dp[i][j],dp[i-1][k]+sum[i][j-k]+(j-k)*(j-k));
			}
		}
	}
	cout << dp[n][n] << endl;
	return 0;
}