题面
最后一次考pj了，居然炸了
s组day1把我心态考崩了，下午j组写了200分就开始颓废，估计要被学弟们嘲笑了QAQ
好了，开始事后诸葛
思路
n个物品，t天价格，数据范围不大，但是直接推转移方程不太可行
想到背包（考场上脑子里“背包”两字都没出现）
先考虑\(n=1\)的情况：
可以把t天的价格中，相邻两天的价格差当作一个物品（\(price=a[i],value=a[i+1]-a[i]\)）
f[i]表示花费i金币的最大收益（不包括本金）
可以自己手玩一下，同时选物品\(i\)和\(i+1\)收益就是\(a[i+2]-a[i]\)，可以连续起来
每一天可以买卖多个，所以是完全背包
注意每天结束之后更新m，毕竟收益也可以用
现在拓展到多个纪念品：
每一天都有n个物品，每个物品的价格还是本身，收益是下一天的减这一天的价格
每一天把n个物品做完全背包，之后更新m
最后得到的m就是答案
坑点是每天背包之前清空f数组
code
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<typename T>
inline void read(T &x) {}
const int N = 105;
const int M = 1e4 + 5;
int t, n, m;
int a[N][N], f[M];
int main() {
read(t), read(n), read(m);
for (int i = 1; i <= t; ++i)
for (int j = 1; j <= n; ++j)
read(a[i][j]);
for (int i = 1; i <= t; ++i) {
memset(f, 0, sizeof f);
for (int j = 1; j <= n; ++j)
for (int k = a[i][j]; k <= m; ++k)
f[k] = max(f[k], f[k - a[i][j]] + a[i+1][j] - a[i][j]);
m = max(m, f[m] + m);
}
printf("%d\n", m);
return 0;
}
|
话说今年pj比去年水的多，比tg良心