链接：https://ac.nowcoder.com/acm/contest/80259/E
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
小红拿到了一个 n ∗ n 的方格矩阵。她准备划分成若干个大小为 3 的 'L' 型连通块和若干个大小为 4 的 2 * 2 连通块。已知每个 'L' 型连通块可以获得 x 分，每个 2 * 2 的连通块可以获得 y 分。小红想知道自己最多可以得到多少分？
输入描述:
三个正整数 n, x, y 用空格隔开。
1 ≤ n, x, y ≤ 1e6
保证 n 是偶数。
输出描述:
小红最大的得分。
示例1
输入
2 4 3
输出
4
说明
可以划分一个 'L' 型连通块。
示例2
输入
4 4 5
输出
21
说明
如下图，可以划分出 4 个 'L' 型连通块和一个 2 * 2 的连通块，这样的得分是最高的。
解答
- 四个格子价值 y，三个格子的 L 型价值 x，如果 y/4 >= x/3，铁定用 y 了，而且还能铺满，否则，考虑 r = n mod 3 的分类讨论：
- 为啥考虑 mod 3，因为两个 L 构成一个方形，能铺满，所以先把前面铺满的地方用 L 铺满，前面价值一定比四个格子的大
- 考虑后面无法用 L 铺满情况：
- r 为 0，显然可以铺满；
- r 为 2，那么可以尽量铺满，先横着放（2x3 的两个 L ）直到剩下两列，在这两列再竖着放，直到剩下一个 2x2 的，看这个 2x2 的铺 L 还是四个格子价值大
- r 为 1，比较复杂，可以先横着 L，剩下 4 列，再双列竖着 L，直到剩下 4x4 的空位，看 5 个 L 和 4 个方块 + 1 个 L 谁大
- 这里为啥不是由每个格子贡献决定，因为前面都是铺满状态，我们通过比较每个格子贡献，那么贡献大的一定最优，但是这里最后无法铺满情况，虽然可能单个格子 L 大，但是方块量大，可能会弥补这个差距，成为最优
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
int main()
{
LL n, x, y;
cin >> n >> x >> y;
if (x * 4 > y * 3)
{
if (n % 3 == 0)
cout << (n * n / 3) * x << endl;
else if (n % 3 == 1)
cout << ((n * n - 16) / 3) * x + max(x * 5, x * 4 + y) << endl;
else
cout << ((n * n - 4) / 3) * x + max(x, y) << endl;
}
else
cout << (n * n / 4) * y << endl;
return 0;
}