自动搬运

查看原文

来自洛谷，原作者为

	miemieQWQ **

搬运于2025-08-24 21:35:04，当前版本为作者最后更新于2017-10-21 20:19:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

蒟蒻的心路历程:{

1.这不是贪心吗?

倒着来, 一格一格查最最优, 样例都没过直接交, 得分20...

2.这不是枚举吗?

假装思考一遍: 激光塔和 放射塔 或 干扰塔 交换位置, 伤害量只会大,

不会小. 干扰塔和放射塔交换位置, 伤害范围增多了一格, 伤害量增大.

所以最后得知防御塔顺序为一堆放射塔、一堆干扰塔、再来一堆激光塔.

嗯, 那么枚举i(放射塔开始位置)和j(激光塔开始位置)问题解决, 20分?

3.这原来是dp啊!

经过分析可以知道第一个塔必定为放射塔, 最后几个塔也必定是激光塔,

但中间放射塔和干扰塔却是镶嵌分布的. 所以只能动态来求解咯!

得分50 →70 →0(MLE) →80 →100

4.关于高精

需要高精加法和乘法, 考虑数据最后也不会太大, __int128还可以搞定!

高精记得要分类讨论, 前60%的数据不要用高精(否则MLE, 没有压位).

} 大致解题思路:{

1.原理:

用dp[i][j]表示在"前面"放i个干扰塔、j个放射塔所产生的最大伤害值,

每一步都可以通过dp[i-1][j]或dp[i][j-1]转移而来, 并且与顺序无关,

剩下n-i-j个格子全放激光塔. //i, j, n-i-j ∈[0, n]

最终答案ans = max{dp[i][j] + jg * (T+gr*i) * (n-i-j)};

2.边界:

dp[0][j] = dp[0][j-1] + fs * (n-j) * T; //fs 放射塔每格伤害

3.状态转移方程:

dp[i][j] = max(dp[i-1][j] + ①, dp[i][j-1] + ②);

①添置干扰塔的伤害: fs * j * gr * (n-i-j) //gr 干扰塔每格减速

②添置放射塔的伤害: fs * (T+gr*i) * (n-i-j) //jg 激光塔每格伤害

} 测试数据:{

10%的数据满足只有干扰塔、激光塔

30%的数据满足只有两种防御塔

60%的数据不需要高精度

另外40%的数据需要40位以内的高精

//不要问我为什么知道的那么清楚, 下面数据仅供参考

(输入1: 400 2147483647 2147483647 2147483647 1000)

(输出1: 24504193721991962785921500) //别数了26个

(输入2: 1024 65536 65536 65536 3)

(输出2: 383746102307848192) //别数了18个

} 贴一份__int128的代码, 高精读起来太费力!

#include<bits/stdc++.h>
#define LONG __int128
using namespace std;

const int N = 1050, M = 30;
LONG dp[N][N] = {0}, ans = 0;
int n, r, g, b, T;

inline void PRINT(LONG x, const string &s)
{
    const long long Base = 1000000000000000000;
    long long l = x / Base, r = x % Base;
    if (l) printf("%lld%18lld", l, r);
    else printf("%lld", r); putchar(s[0]);
}

int main()
{
    cin >>n >>r >>g >>b >>T;
    const LONG jg = r, fs = g, gr = b;
    const LONG fsgr = fs * gr, fsT = fs * T;
    const LONG jggr = jg * gr, jgT = jg * T;

    //i(干扰塔个数), j(放射塔个数) , k(激光塔个数) ↓
    for (int j = 1; j <= n; j++) //边界 
        dp[0][j] = dp[0][j-1] + fsT * (n-j);
    for (int i = 1; i < n; i++)
        for (int j = 1, k; k = n - i - j; j++)
            dp[i][j] = max(dp[i-1][j] + fsgr * j * k,
                           dp[i][j-1] + (fsgr * i + fsT) * k);
    
    for (int i = 0; i < n; i++) //加上激光塔求最大值 
        for (int j = 0, k; k = n - i - j; j++)
            ans = max(ans, dp[i][j] + (jggr * i + jgT) * k);
    PRINT(ans, "\n");
    return 0;
}