<0x0D> 5倍经验日
题目背景
现在乐斗有活动了！每打一个人可以获得 5 倍经验！
absi2011 却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。
题目描述
现在 absi2011 拿出了 $x$ 个迷你装药物（嗑药打人可耻…），准备开始与那些人打了。
由于迷你装药物每个只能用一次，所以 absi2011 要谨慎的使用这些药。
悲剧的是，用药量没达到最少打败该人所需的属性药药量，则打这个人必输。
例如他用 $2$ 个药去打别人，别人却表明 $3$ 个药才能打过，那么相当于你输了并且这两个属性药浪费了。
现在有 $n$ 个好友，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药量。
要求求出最大经验 $s$，输出 $5s$。
输入格式
第一行两个数，$n$ 和 $x$
后面 $n$ 行每行三个数，分别表示失败时获得的经验 $\mathit{lose}_i$
胜利时获得的经验 $\mathit{win}_i$ 和打过要至少使用的药数量 $\mathit{use}_i$。
输出格式
一个整数，最多获得的经验的五倍。
样例
样例输入
6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2
样例输出
1060
提示
【Hint】
五倍经验活动的时候，absi2011 总是吃体力药水而不是这种属性药。
【题目来源】
fight.pet.qq.com
absi2011 授权题目
数据规模与约定
- 对于 $10%$ 的数据，保证 $x=0$。
- 对于 $30%$ 的数据，保证 $0\le n\le 10$，$0\le x\le 20$。
- 对于 $60%$ 的数据，保证 $0\le n,x\le 100$， $10<lose_i,win_i\le 100$，$0\le use_i\le 5$。
- 对于 $100%$ 的数据，保证 $0\le n,x\le 10^3$，$0<lose_i\le win_i\le 10^6$，$0\le use_i\le 10^3$。
分析
嗯，动态规划，我们都知道
但是怎么动态规划呢
看到这样的题，首先要去想状态转移方程会是怎么样的
根据之前的经验，大概是这样$f(i,j)$
其中$i$表示处理前$i$个数据，$j$表示已经用了$j$瓶药
那总体的逻辑就很像背包dp了
但这个也不同于经典背包dp，还需要处理输了的情况
这就导致状态转移不止一个式子，我这里写不明白就不写了
代码
#include <iostream>
#include <vector>
// 封装一个敌人类
class Enemy
{
public:
int lose;
int win;
int use;
Enemy(int lose, int win, int use)
{
this->lose = lose;
this->win = win;
this->use = use;
}
};
int main()
{
// 读入
int n, x;
std::cin >> n >> x;
std::vector<Enemy> list;
for (int i = 0; i < n; i++)
{
int a, b, c;
std::cin >> a >> b >> c;
list.push_back(Enemy(a, b, c));
}
// 初始化第一个状态
std::vector<size_t> map(x + 1);
map[0] = list[0].lose;
if (list[0].use <= x)
{
map[list[0].use] = list[0].win;
}
// 开始dp
for (int i = 1; i < n; i++)
{
// 注意循环方向
for (int j = x; j >= 0; j--)
{
if (map[j] == 0)
{
continue;
}
// 处理剩下的药够嗑的情况
if (j + list[i].use <= x)
{
map[j + list[i].use] = std::max(map[j + list[i].use], map[j] + list[i].win);
}
// 处理不需要嗑药的情况
if (list[i].use != 0)
{
map[j] += list[i].lose;
}
}
}
// 遍历最大值
size_t ans = 0;
for (auto i : map)
{
ans = std::max(ans, i);
}
// 乘5输出
std::cout << ans * 5 << "\n";
return 0;
}
遇到的坑
因为省略状态转移方程的第一个参数，所以要注意循环方向
还有就是当某个敌人不需要嗑药也能打过的时候需要特殊处理
如果不处理会导致赢了和输了都计算一遍
<0x0E> 最大子段和
题目描述
给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数，表示序列的长度 $n$。
第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。
输出格式
输出一行一个整数表示答案。
样例
样例输入
7
2 -4 3 -1 2 -4 3
样例输出
4
样例解释
选取 $[3, 5]$ 子段 ${3, -1, 2}$，其和为 $4$。
数据规模与约定
- 对于 $40%$ 的数据，保证 $n \leq 2 \times 10^3$。
- 对于 $100%$ 的数据，保证 $1 \leq n \leq 2 \times 10^5$，$-10^4 \leq a_i \leq 10^4$。
分析
这道题需要贪心+dp的思路
对于样例的数据
从2开始，$2+(-4)=-2<2$
这意味着如果答案包含-4，那么也一定包含前面的2，不如就很难把数字撑大
接着加，$(-2)+3=1<3$，这意味着如果答案包含-4，那么也会包含这个3
而且会发现，接着这条链不如新开一条链，因为前面的数字相当于累赘
所以从3开始加，$3+(-1)=2>-1$，$2+2=4>2$，$4+(-4)=0>-4$，$0+3=3=3$
这里也发现一个问题，之前写的动态规划的题一般最后的状态就是答案
但这里的答案在过程中间，所以需要一个存储最大值的变量
所以最后的状态转移方程是$f(i)=max(a_i,f(i-1)+a_i)$
其中，$i$表示已处理前$i$个数据，$a_i$是输入的数组
代码
#include <iostream>
#include <limits.h>
#include <vector>
int main()
{
// 读入
int n;
std::cin >> n;
std::vector<long long> list(n);
for (int i = 0; i < n; i++)
{
std::cin >> list[i];
}
// 初始化第一个状态
std::vector<long long> map(n);
map[0] = list[0];
long long ans = INT_MIN;
for (int i = 1; i < n; i++)
{
// 如果前面加上的还不如新开一条的话就丢弃
map[i] = std::max(list[i], map[i - 1] + list[i]);
// 更新答案
ans = std::max(ans, map[i]);
}
std::cout << ans << "\n";
return 0;
}
遇到的坑
一开始想不到贪心+dp的思路
所以是看了题解后才会的题
<0x0F> 滑雪
题目描述
Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激
可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你
Michael 想知道在一个区域中最长的滑坡
区域由一个二维数组给出。数组的每个数字代表点的高度
下面是一个例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小
在上面的例子中，一条可行的滑坡为 $24-17-16-1$（从 $24$ 开始，在 $1$ 结束）
当然 $25-24-23-\ldots-3-2-1$ 更长。事实上，这是最长的一条。
输入格式
输入的第一行为表示区域的二维数组的行数 $R$ 和列数 $C$
下面是 $R$ 行，每行有 $C$ 个数，代表高度(两个数字之间用 $1$ 个空格间隔)。
输出格式
输出区域中最长滑坡的长度。
样例
样例输入
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
样例输出
25
数据规模与约定
对于 $100%$ 的数据，$1\leq R,C\leq 100$。
分析
还是动态规划的题，这次就不想状态转移方程了
来试试记忆化搜索
记忆化搜索本质上就是遇到搜索过的地方就直接返回搜索的结果
对于搜索过程中遇到更好的情况也对之前的结果进行更新
一般思路是先写出正常的DFS过程
然后用某种数据结构做记忆化，配合一些条件做结果更新
这样就完成了记忆化搜索的改造
记忆化搜索也是可以转换为状态转移方程的
但状态转移方程不一定能转换成记忆化搜索的
而且一般情况下两个方法的时间空间复杂度差不多
对于这道题，主要就是记忆化搜索的过程
需要注意的是，二维矩阵需要默认初始化为1
因为对于每一段路，长度都是1，默认为0的话就加不出来了
代码
// 带各种封装，所以代码量大
#include <iomanip>
#include <iostream>
#include <vector>
// 点的封装
struct Point
{
public:
int x;
int y;
Point()
{
x = 0;
y = 0;
}
Point(int x, int y)
{
this->x = x;
this->y = y;
}
Point(const Point &c)
{
x = c.x;
y = c.y;
}
};
// 二维矩阵的封装
class Map
{
std::vector<std::vector<int>> _map;
public:
int X;
int Y;
Map(int x, int y)
{
X = x;
Y = y;
_map.resize(y, std::vector<int>(x, 1));
}
Map(const Map &c)
{
X = c.X;
Y = c.Y;
_map.resize(c.Y, std::vector<int>(c.X));
for (int i = 0; i < Y; i++)
{
for (int j = 0; j < X; j++)
{
_map[i][j] = c._map[i][j];
}
}
}
int &At(int x, int y)
{
return _map[y][x];
}
int &At(Point &p)
{
return _map[p.y][p.x];
}
};
// DFS搜索的封装
class DFS
{
// 记忆化矩阵
Map _mem;
int dfs(Map &m, Point p)
{
// 如果已经搜索过就返回
if (_mem.At(p) != 1)
{
return _mem.At(p);
}
// 4方向遍历
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
for (int i = 0; i < 4; i++)
{
int tx = p.x + dx[i];
int ty = p.y + dy[i];
// 出界判断
if (tx < 0 || ty < 0)
{
continue;
}
if (tx >= _mem.X || ty >= _mem.Y)
{
continue;
}
// 条件判断
if (m.At(p) > m.At(tx, ty))
{
// 取最大值
_mem.At(p) = std::max(_mem.At(p), dfs(m, Point(tx, ty)) + 1);
}
}
// 更新全局最大值
max = std::max(max, _mem.At(p));
return _mem.At(p);
}
public:
int max = 0;
DFS(Map &m) : _mem(m.X, m.Y)
{
// 遍历所有起始点
for (int i = 0; i < m.X; i++)
{
for (int j = 0; j < m.Y; j++)
{
dfs(m, Point(i, j));
}
}
}
};
int main()
{
// 读入
int r, c;
std::cin >> r >> c;
Map map(c, r);
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
std::cin >> map.At(j, i);
}
}
// 计算
DFS ans(map);
// 输出
std::cout << ans.max << "\n";
return 0;
}
遇到的坑
有笨比最后没有遍历所有起点，导致Debug半天
因为有可能会分多个区域，一次遍历是不够的
<0x10> 小A点菜
题目背景
uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。
uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。
题目描述
不过 uim 由于买了一些书，口袋里只剩 $M$ 元 $(M \le 10000)$。
餐馆虽低端，但是菜品种类不少，有 $N$ 种 $(N \le 100)$，第 $i$ 种卖 $a_i$ 元 $(a_i \le 1000)$
由于是很低端的餐馆，所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”的原则，所以他点单一定刚好把 uim 身上所有钱花完
他想知道有多少种点菜方法。
由于小 A 肚子太饿，所以最多只能等待 $1$ 秒。
输入格式
第一行是两个数字，表示 $N$ 和 $M$。
第二行起 $N$ 个正数 $a_i$（可以有相同的数字，每个数字均在 $1000$ 以内）。
输出格式
一个正整数，表示点菜方案数，保证答案的范围在 int 之内。
样例
样例输入
4 4
1 1 2 2
样例输出
3
分析
一道简单的计数dp的题，逻辑上跟之前的摆花差不多
需要解决的是怎么把点菜方式统计转换为一个递推的关系
以样例举例
根据之前的经验，状态转移方程大概长这样$f(i,j)$
其中$i$表示处理了前$i$个数据，$j$表示花了$j$元钱
其中，$i\in[0,n-1],j\in[0,m]$，因为花了0元也算花钱
然后先把每个情况的值都列出来，再看看有什么规律
i→
j * 1 1 2 2
↓ 0 1 1 1 1
1 1 2 2 2
2 0 1 2 3
3 0 0 2 4
4 0 0 1 3
不难发现，状态转移方程是$f(i,j)=f(i-1,j-a_i)+f(i-1,j)$
如果$j-a_i<0$那么$f(i-1,j-a_i)=0$
怎么理解这个方程呢
假设此时遍历到了最后一个2，我们要计算花了3元的情况
这时候，对于前面花了1元的情况，只要再点这个2元的菜就凑够了3元
对于前面已经花了3元的情况，不点这个菜也够了3元
所以这两个的值相加就是此时花3元的方法总数
因为遍历过程中，仅考虑了$i$和$i-1$的情况，所以可以省略$i$这个维度
可以进一步压缩空间，但要注意遍历顺序
代码
#include <iostream>
#include <vector>
int main()
{
// 读入
int n, m;
std::cin >> n >> m;
std::vector<int> list(n);
for (int i = 0; i < n; i++)
{
std::cin >> list[i];
}
// 初始化第一个状态
std::vector<std::vector<int>> dp(n, std::vector<int>(m + 1));
dp[0][0] = 1;
dp[0][list[0]] = 1;
// 开始dp
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= m; j++)
{
if (j - list[i] >= 0)
{
dp[i][j] = dp[i - 1][j - list[i]] + dp[i - 1][j];
}
else
{
dp[i][j] = dp[i - 1][j];
}
}
}
// 输出最后一个值
std::cout << dp[n - 1][m] << "\n";
return 0;
}