AtCoder ABC 263 D 题解
前言
本蒟蒻的第一篇题解，大佬勿喷 QwQ
传送门们
正文
设有 \(x\) 使得 \(x\leq k\) 时，令 \(f(k)\) 为对 \(A'\) 进行运算后 \(A'=(A_1,A_2,\ldots,A_k)\) 的最小和。
同理，对于 \(y\) 使得 \(y\leq k\) 时，令 \(g(k)\) 为对 \(A''\) 进行运算后 \(A''=(A_{N-k+1},\ldots,A_N)\) 的最小和。
如果我们能求出 \(f(0),f(1),\ldots,f(N),g(0),g(1),\ldots,g(N)\)，那么答案就是 \(\min(f(i)+g(N-i))\)。
我们设 \(f(0)=0\)。要想求得 \(f(k+1)\)，我们需要先求得 \(f(k)\)。这取决于是否有 \(x<k+1\)。
分类讨论
-
如果 \(x<k+1\)，则最小和为 \(f(k)+A_{k+1}\)。
-
如果 \(x=k+1\)，则最小和为 \(L(k+1)\)。
因此，我们可以求得 \(f(k+1)=\min(f(k)+A_{k+1},L(k+1))\)。
同理可求得 \(g(k)\)，时间复杂度 \(\mathrm{O}(N)\)。
AC Code
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, l, r;
cin >> n >> l >> r;
long long pre = 0, ans = 1LL * r * n;
for(int i = 1, a; i <= n; ++i) {
cin >> a;
pre = min(pre + a, 1LL * i * l);
ans = min(ans, pre + 1LL * (n - i) * r);
}
cout << ans;
return 0;
}