这两题并不难，写这篇博客的原因是觉得这两题挺好玩的hhhhhhh
最大乘积
题目描述
一个正整数一般可以分为几个互不相同的自然数的和，如 $3=1+2$，$4=1+3$，$5=1 + 4 = 2 + 3$，$6=1+5=2+4$。
现在你的任务是将指定的正整数 $n$ 分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。
输入格式
只一个正整数 $n$，（$3 \leq n \leq 100003$）。
输出格式
第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。
第二行是最大的乘积。
输入输出样例
输入
10
输出
2 3 5
30
思路
这题有贪心的做法，但不是很好理解，这里给一个很好理解但是很low的01背包的做法。
题目可将其理解为从$1,2,3....n$，这 $n$ 个数中选出一些数，使得它们的和为 $n$。但是学过01背包的同学就会问了，01背包不是处理从$a$个物品中选，最大容量为$b$的最大价值和吗？而这题要我们求的是最大乘积呀？
这里就要用到数学里面对数的性质了。
$$
lna \ + \ lnb = ln(a \ \times \ b)
$$
所以我们如果要乘积最大的话，那只要对应对数和最大就可以了。
最后写个高精度乘低精度就可以了
高精度乘低精度模板
vector<int> mul(vector<int>& A, int k)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * k;
C.push_back(t % 10);
t /= 10;
}
while (C.size() && C.back() == 0) C.pop_back();
return C;
}
参考代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
double f[N], w[N];
int p[N];
vector<int> mul(vector<int>& A, int k)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * k;
C.push_back(t % 10);
t /= 10;
}
while (C.size() && C.back() == 0) C.pop_back();
return C;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) w[i] = log(i);
for (int i = 1; i <= n; i ++ )
for (int j = n; j >= i; j -- )
if (f[j - i] + w[i] > f[j])
{
f[j] = f[j - i] + w[i];
p[j] = j - i;
}
vector<int> A, res(1, 1);
for (int i = n; i ; i = p[i] ) A.push_back(i - p[i]);
for (int i = A.size() - 1; i >= 0; i -- )
{
auto C = mul(res, A[i]);
res = C;
cout << A[i] << ' ';
}
cout << endl;
for (int i = res.size() - 1; i >= 0; i -- ) cout << res[i];
cout << endl;
return 0;
}
题目链接：P1249 最大乘积
刺杀大使
题目描述
某组织正在策划一起对某大使的刺杀行动。他们来到了使馆，准备完成此次刺杀，要进入使馆首先必须通过使馆前的防御迷阵。
迷阵由 $n \times m$ 个相同的小房间组成，每个房间与相邻四个房间之间有门可通行。在第 $n$ 行的 $m$ 个房间里有 $m$ 个机关，这些机关必须全部打开才可以进入大使馆。而第 $1$ 行的 $m$ 个房间有 $m$ 扇向外打开的门，是迷阵的入口。除了第 $1$ 行和第 $n$ 行的房间外，每个房间都被使馆的安保人员安装了激光杀伤装置，将会对进入房间的人造成一定的伤害。第 $i$ 行第 $j$ 列 造成的伤害值为 $p_{i,j}$（第 $1$ 行和第 $n$ 行的 $p$ 值全部为 $0$）。
现在某组织打算以最小伤害代价进入迷阵，打开全部机关，显然，他们可以选择任意多的人从任意的门进入，但必须到达第 $n$ 行的每个房间。一个士兵受到的伤害值为他到达某个机关的路径上所有房间的伤害值中的最大值，整个部队受到的伤害值为所有士兵的伤害值中的最大值。现在，这个恐怖组织掌握了迷阵的情况，他们需要提前知道怎么安排士兵的行进路线可以使得整个部队的伤害值最小。
输入格式
第一行有两个整数 $n,m$，表示迷阵的大小。
接下来 $n$ 行，每行 $m$ 个数，第 $i$ 行第 $j$ 列的数表示 $p_{i,j}$。
输出格式
输出一个数，表示最小伤害代价。
输入输出样例
输入
4 2
0 0
3 5
2 4
0 0
输出
3
说明/提示
$50%$ 的数据，$n,m \leq 100$；
$100%$ 的数据，$n,m \leq 1000$，$p_{i,j} \leq 1000$。
思路
一道很明显的二分 + bfs的题目，别问为什么不用dfs做，因为TLE＞﹏＜了。
参考代码
二分模板
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
完整代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1010, INF = 1e9;
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int g[N][N], mark[N][N];
bool check(int mid)
{
memset(mark, 0, sizeof mark);
queue<PII> q;
q.push({1, 1});
mark[1][1] = 1;
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a >= 1 && a <= n && b >= 1 && b <= m && !mark[a][b] && g[a][b] <= mid)
{
if (a == n) return true;
mark[a][b] = 1;
q.push({a, b});
}
}
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &g[i][j]);
int l = 0, r = 1000;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", r);
return 0;
}
题目链接：P1902 刺杀大使
评论