解题思路
激光塔一定在最后。\(f_{i,j}\) 表示前 \(i\) 个位置放 \(j\)(\(j\le i\))个放射塔,那么 \(i-j\) 个干扰塔的伤害。
若第 \(i\) 个位置放放射塔:\(f_{i,j}=f_{i-1,j-1}+(j-1)\times g\times[t+b\times(i-j)]\)
若第 \(i\) 个位置放干扰塔,也就是 \(j<i\):\(f_{i,j}=\max\{f_{i-1,j-1}+(j-1)\times g\times[t+b\times(i-j)],f_{i-1,j}+j\times g\times[t+b\times(i-j-1)]\}\)。
最终答案为 \(\max\limits_{0\le j\le i\le n}\{f_{i,j}+(n-i)\times(r+j\times g)\times[t+b\times(i-j)]\}\)。
由于答案过大,所以建议开 __int128_t
或者高精度。
代码
#include<bits/stdc++.h>
using namespace std;
__int128_t n, r, g, b, t, ans, f[1030][1030];
inline __int128_t read() {
__int128_t x = 0;
bool flag = 0;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') {
flag = 1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
if(!flag) {
return x;
} else {
return -x;
}
}
inline void write(__int128_t x) {
if(x < 0) {
x = -x;
putchar('-');
}
if(x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
int main() {
n = read(), r = read(), g = read(), b = read(), t = read();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= i; j++) {
f[i][j] = f[i - 1][j - 1] + (j - 1) * g * (t + b * (i - j));
if(i != j) {
f[i][j] = max(f[i][j], f[i - 1][j] + j * g * (t + b * (i - j - 1)));
}
}
}
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= i; j++) {
ans = max(ans, f[i][j] + (n - i) * (r + j * g) * (t + b * (i - j)));
}
}
write(ans);
return 0;
}
标签:__,ch,read,题解,times,le,P2198,int128
From: https://www.cnblogs.com/cyf1208/p/17773533.html