题目大意
有一条长度为 \(n\) 个单位长度的路，蚂蚁们要从起点走到终点。蚂蚁们每走 \(1\) 个单位距离需要 \(T\) 秒钟。现在，出题人可以在路上修筑 \(3\) 种防御塔来阻挡蚂蚁的进攻，每个单位距离只能修筑 \(1\) 座塔，塔的作用分别如下：
-
激光塔：蚂蚁在塔前时每秒会受到 \(r\) 点伤害。
-
放射塔：蚂蚁经过塔后，每秒钟受到 \(g\) 点伤害。
-
干扰塔：蚂蚁经过塔后，每行走一个单位距离的时间延长为 \(T + b\)。
其中，放射塔和干扰塔的效果可以叠加。比如蚂蚁经过了 \(y\) 座放射塔后，每秒钟受到的伤害为 \(yr\)，干扰塔同理。
现在需求能给蚂蚁们造成的最大伤害。
解法
分析题目，题目需要求一个最大值，且不在意中间过程，因此我们可以考虑 dp。
设 \(dp_{i, j, k}\) 表示修 \(i\) 座干扰塔，\(j\) 座放射塔，\(k\) 座激光塔的最大伤害。显然，每个位置都修塔是最优的，因此，我们可以省掉一维 \(k\)，需要用时直接计算即可。
关于如何转移，枚举干扰塔和放射塔的个数 \(i, j\)，\(dp_{i, j}\) 可以由 \(dp_{i - 1, j}, dp_{i, j - 1}\) 转移过来，也就是对于上一个状态来说，少一座激光塔，多一座干扰塔或少一座激光塔，多一座放射塔。那么 \(dp_{i, j} = \max(dp_{i - 1, j} - r\times(t + b(i - 1)) + b\times(n - i - j)(r + g\times j), dp_{i, j - 1} - t\times r - i\times b\times r + g\times(n - i - j)(t + b\times i)\)。多一座干扰塔，就要将一座激光塔所造成的伤害减去，加上时间延长放射塔所造成的伤害。多一座放射塔，也要讲一座激光塔的伤害减去，然后加上一座放射塔所造成的伤害。
边界的处理和转移差不多，就是此时只有两种塔，比转移少简单一些。需要注意的是全是激光塔的情况也需要处理，也就是 \(dp_{0, 0} = t\times r\times n\)。
由于此题答案可能过大，整数变量需要定义为 __int128，且 __int128 无法使用 cin、cout、scanf、printf 等进行输入输出，所以请手写快读快写。
AC Code
#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int N = 2e3 + 5;
int n, r, g, b, t, dp[N][N], ans;
int read()
{
int k = 1, t = 0;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-')
k *= -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
t = t * 10 + c - '0';
c = getchar();
}
return k * t;
}
void write(int x)
{
int b[50], cnt = 0;
while(x != 0)
{
int y = x % 10;
x /= 10;
b[++cnt] = y;
}
for(int i = cnt; i >= 1; i--)
putchar(b[i] + '0');
return;
}
signed main()
{
n = read(), r = read(), g = read(), b = read(), t = read();
memset(dp, 0xcf, sizeof(dp));
dp[0][0] = n * t * r;
ans = dp[0][0];//处理边界
for(int i = 1; i <= n; i++)
{
dp[i][0] = dp[i - 1][0] - (t + (i - 1) * b) * r + (n - i) * b * r;
dp[0][i] = dp[0][i - 1] - t * r + (n - i) * t * g;
ans = max(ans, max(dp[0][i], dp[i][0]));
}
for(int i = 1; i <= n; i++)//转移
for(int j = 1; j + i <= n; j++)
dp[i][j] = max(dp[i - 1][j] - (t + (i - 1) * b) * r + (n - i - j) * b * (r + g * j), dp[i][j - 1] - t * r - i * (b * r) + (n - i - j) * (t + b * i) * g);
for(int i = 1; i <= n; i++)//答案为最大值
for(int j = 1; j + i <= n; j++)
ans = max(ans, dp[i][j]);
write(ans);
return 0;
}