国王游戏与皇后游戏

国王游戏

首先，每个人在左、右手上面分别有一个整数。然后，$N$位大臣排成一排，国王站在队伍的最前面。每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。现在要使金币的最大值最小

可以来试着推一下
先把关系设好
假设加上国王只有下面三个人（大臣$Minister$用$M$表示，金币用$C$）

人	左手	右手
$King$	$a_0$	$b_0$
$M1$	$a_1$	$b_1$
$M2$	$a_2$	$b_2$

当前答案：
\begin{aligned}
ans &= max(C_{M1},C_{M2}) \\
&= max(\frac{a_0}{b_1},\frac{a_0 \times a_1}{b_2})
\end{aligned}
两位大臣交换后：
\begin{aligned}
ans &= max(C_{M2},C_{M1}) \\
&= max(\frac{a_0}{b_2},\frac{a_0 \times a_2}{b_1})
\end{aligned}
假设不交换更优
那么$max(\frac{a_0}{b_2},\frac{a_0 \times a_2}{b_1})>max(\frac{a_0}{b_1},\frac{a_0 \times a_1}{b_2})$
设这四项分别为$A,B,C,D$
显然$B>C,D>A$
又有$max(A,B)>max(C,D)$
这个$A$是随便插空都可以的
但可知$D$一定大于$B$
即$\frac{a_0 \times a_2}{b_1}>\frac{a_0 \times a_1}{b_2}$
所以$\frac{a_2}{b_1}>\frac{a_1}{b_2}$
得出不等式$a_1 \times b_1 < a_2 \times b_2$
结论$->$按$a \times b$从小到大排序会使答案更优
国王游戏就是这样
比较简单
But要高精
传送门
代码：压了一丢丢行

#include <iostream>
#include <complex>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
namespace BigInteger {
    struct Big_integer {
        int d[10005], len;
        void clean() {while(len > 1 and !d[len - 1]) len--;}
        Big_integer() {memset(d, 0, sizeof d); len = 1;}
        Big_integer(int num) {*this = num;}
        Big_integer operator = (const char* num) {
            memset(d, 0, sizeof d); len = strlen(num);
            for (int i = 0; i < len; i++) d[i] = num[len - 1 - i] - '0';
            clean(); return *this;
        }
        Big_integer operator = (int num) {
            char s[10005]; sprintf(s, "%d", num);
            *this = s; return *this;
        }
        Big_integer operator * (const Big_integer &b) const {
            int i, j; Big_integer c;
            c.len = len + b.len;
            for (j = 0; j < b.len; j++)
                for (i = 0; i < len; i++)
                    c.d[i + j] += d[i] * b.d[j];
            for (i = 0; i < c.len - 1; i++) c.d[i + 1] += c.d[i] / 10, c.d[i] %= 10;
            c.clean(); return c;
        }
        Big_integer operator / (const int &b) {
            int i, j, a = 0; Big_integer c = *this;
            for (i = len - 1; i >= 0; i--) {
                a = a * 10 + d[i];
                for (j = 0; j < 10; j++) if (a < b * (j + 1)) break;
                c.d[i] = j;
                a = a - b * j;
            }
            c.clean(); return c;
        }
        bool operator < (const Big_integer &b) const {
            if (len != b.len) return len < b.len;
            for (int i = len - 1; i >= 0; i--)
                if (d[i] != b.d[i])
                    return d[i] < b.d[i];
            return false;
        }
        string str() const {
            char s[10005];
            for (int i = 0; i < len; i++) s[len - 1 - i] = d[i] + '0';
            return s;
        }
    };
    istream& operator >> (istream& in, Big_integer &x) {
        string s; in >> s;
        x = s.c_str(); return in;
    }
    ostream& operator << (ostream& out, const Big_integer &x) {
        out << x.str();
        return out;
    }
}
using namespace BigInteger;
struct node {
    int a, b;
    friend bool operator < (const node x, const node y) {
        return x.a * x.b < y.a * y.b;
    }
}e[10010];
int n;
Big_integer ans, tmp = 1;

int main(int argc, char const *argv[]) {
    scanf("%d%d%d", &n, &e[1].a, &e[1].b);
    for (int i = 2; i <= n + 1; i++) scanf("%d%d", &e[i].a, &e[i].b);
    sort(e + 2, e + n + 2);
    for (int i = 2; i <= n + 1; i++) tmp = tmp * e[i - 1].a, ans = max(ans, tmp / e[i].b);
    cout << ans << endl;
}

再看麻烦点的皇后游戏

皇后游戏

皇后有$N$位大臣，每位大臣的左右手上面分别写上了一个正整数。要为$N$位大臣颁发奖金，其中第$i$位大臣所获得的奖金数目为第$i-1$位大臣所获得奖金数目与前$i$位大臣左手上的数的和的较大值再加上第$i$位大臣右手上的数。
即：设第$i$位大臣左手上的正整数为$a_i$，右手上的正整数为$b_i$，则第$i$位大臣获得的奖金数目为$C_i$可以表达为：$c_{i}=\left\{\begin{array}{cc}{a_{1}+b_{1}} & {i=1} \\{\max \left\{c_{i-1}, \sum_{j=1}^{i} a_{j}\right\}+b_{i}} & {2 \leq i \leq n}\end{array}\right.$

可以仿照着国王游戏自己yy一下
来看怎么做
我们还是假设两个大臣编号为$i$和$j$
设$C_{i-1}=Y,\sum_{k=1}^{i-1} a_k=X$
则当前答案为：
\begin{aligned} \text {ans} &=\max \left(C_{M_{i}}, C_{M_{j}}\right) \\
&=\max \left(\max \left(Y, X+a_{i}\right)+b_{i}, X+a_{i}+a_{j}\right) )+b_{j} \\
&=\max \left(Y+b_{i}+b_{j}, X+a_{i}+b_{i}+b_{j}, X+a_{i}+a_{j}+b_{j}\right)
\end{aligned}
交换两位大臣的位置后：
\begin{aligned} \text {ans} &=\max \left(C_{M_{J}}, C_{M_{i}}\right) \\
&=\max \left(\max \left(Y, X+a_{j}\right)+b_{j}, X+a_{i}+a_{j}\right) )+b_{i} \\
&=\max \left(Y+b_{i}+b_{j}, X+a_{j}+b_{i}+b_{j}, X+a_{i}+a_{j}+b_{i}\right)
\end{aligned}
假设交换更优
那么第二个等式大于第一个等式
发现两边都有$Y+b_i+b_j$，消去：
$max(X+a_j+b_i+b_j,X+a_i+a_j+b_i)>max(X+a_i+b_i+b_j,X+a_i+a_j+b_j)$
再把共同的$X$提出来：
$max(a_j+b_i+b_j,a_i+a_j+b_i)>max(a_i+b_i+b_j,a_i+a_j+b_j)$
把两边分别共有的拿出来：
$max(b_j,a_i)+a_j+b_i>max(b_i,a_j)+a_i+b_j$
移项：
$max(b_j,a_i)-a_i-b_j>max(b_i,a_j)-a_j-b_i$
可知两个中大的会被减掉然后剩下小的那个的相反数
即$-min(b_i,a_i)>-min(b_j,a_j)$
最后得到：$min(a_i,b_j)<min(a_j,b_i)$
又是一个简单式子