\(Problem\)
给你\(n\)和长度为\(n\)的数组\(a[]\)。
可以使\(a[i]\)增加成\(a[i]'\)，其代价为\(a[i]'-a[i]\)。
求花费最小的代价使得满足对于任意的\(i \in [2,n]\)，\(L<=a[i-1]+a[i]<=R\)，\(L,R\)为给定的数。
\(n<=10^5.L,R<=10^6\)
\(force\)
首先有一个显然的暴力\(DP\)。
设\(f[i][x]\)表示\(a[i]\)变成\(x\)前面都满足条件的最小代价。
则\(f[i][x]\)可以转移到\(f[i+1][k]\)，\(k\in [L-x,R-x]\)
然后可以发现，当\(a[i]>=L\)的时候，再增加其实没有什么意义的。
所以枚举的界限缩小，时间复杂度为\(O(n*L^2)\)，\(35\)分到手。
\(Solution\ 1\)
考虑可撤销贪心，顺序改变值，只考虑\(i\)以前的都符合条件。
设\(pl[i]\)表示\(a[i]\)要加的数。
对于当前位置\(i\)：
设\(sum=a[i - 1] + a[i] + pl[i - 1]\)
若\(L<=sum<=R\)，则可以\(a[i]\)不需要改变（即\(pl[i]\)不需要变）
若\(sum<L\)，则\(pl[i]=L-sum\)即可。
若\(sum>R\)，则通过一个\(check(i-1)\)函数来处理一下。
\(check(x)\)函数：
对于新的\(sum=a[i]+a[i+1]+pl[i]+pl[i+1]\)
若当前的\(L<=sum<=R\)，则返回可行（\(1\)）
若当前的\(sum>R\)，则\(pl[i]\)需要减小，并判断是否小于\(0\)。
若当前的\(sum<L\)，则\(pl[i]\)需要增加，并判断\(check(x-1)\)。
如此即可。（看上去似乎可能会\(TLE\)，但是跑得飞快）
#include <cstdio>
#define N 50010
#define db double
#define ll long long
#define mem(x, a) memset(x, a, sizeof x)
#define mpy(x, y) memcpy(x, y, sizeof y)
#define fo(x, a, b) for (int x = (a); x <= (b); x++)
#define fd(x, a, b) for (int x = (a); x >= (b); x--)
#define go(x) for (int p = tail[x], v; p; p = e[p].fr)
using namespace std;
int n, L, R, a[N], pl[N];
ll all = 0;
inline int read() {
int x = 0, f = 0; char c = getchar();
while (c < '0' || c > '9') f = (c == '-') ? 1 : f, c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f ? -x : x;
}
bool check(int x, int sum) {
if (x == 0 || (sum >= L && sum <= R)) return 1;
if (sum > R) {
pl[x] -= sum - R;
if (pl[x] < 0) return 0;
return check(x - 1, a[x - 1] + a[x] + pl[x - 1] + pl[x]);
}
pl[x] += L - sum;
return check(x - 1, a[x - 1] + a[x] + pl[x - 1] + pl[x]);
}
int main()
{
freopen("plan.in", "r", stdin);
freopen("plan.out", "w", stdout);
n = read(), L = read(), R = read();
fo(i, 1, n) a[i] = read();
fo(i, 2, n) {
int sum = a[i - 1] + a[i] + pl[i - 1];
if (sum < L) {pl[i] = L - sum; continue;}
if (sum > R && ! check(i - 1, sum))
return 0 & printf("-1\n");
}
fo(i, 1, n) all += pl[i]; printf("%lld\n", all);
fo(i, 1, n) printf("%d ", a[i] += pl[i]);
/*
fo(i, 2, n)
if (a[i - 1] + a[i] < L || a[i - 1] + a[i] > R)
printf("wrong\n");
*/
return 0;
}
\(Solution\ 2\)
考虑原先的\(DP\)。
性质\(1\)：发现\(f[i,x]\)转移到\(f[i+1,j]\)为一个区间，可以单调队列优化。
性质\(2\)：且又发现转移到的\([l,r]\)，\(f[i+1][j]\)的值是单调不减的。
设\(le[i],ri[i]\)表示对于\(f[i]\)的可行的区间。
则答案就是\(f[n][le[n]]\)，而我们又可以从中倒推出是从\([L-le[n],R-le[n]]\)与\([le[n-1],ri[n-1]]\)的交转移过来的。
而由于\(f[x]\)的单调性，所以一定是交的最左端点最后，这样线性地倒推回去就可以求解了。