题目描述
给出 $(2n+1)\times (2n+1)$ 个点,点 $(i,j)$ 的权值为 $a[max(|i-n-1|,|j-n-1|)]$ ,找一条从 $(1,1)$ 走到 $(2n+1,2n+1)$ 的路径,使得经过的点(包括起点和终点)权值和最小.求这个权值和.
输入
第一行一个正整数 $n$ .
第二行 $n+1$ 个正整数 $a[0],a[1],…,a[n]$ ,表示从内到外每层的中继器的延时值.
输出
输出一行一个数表示改造后的最短引爆时间.
样例输入
输出
9
9 5 3 7 6 9 1 8 2 4
69
题解
CDQ 分治 + 斜率优化 dp
我 tm 就是个傻逼 = = 明明正解就一个贪心我非要写 dp + 斜率优化...
显然所选路径具有对称性,并且是从左上角走到 $(i,i),i\le n+1$ ,然后沿着这个等距离圈走到 $(2n+2-i,2n+2-i)$ ,再按照同样的路径返回.
设 $f[i]$ 表示到点 $(i+1,i+1)$ 的最小代价.
设 $b[i]=a[n-1-i]$ (为了方便从外层向内层递推)
正解:从 $i$ 到 $i+1$ 显然是通过 $1~i$ 中最小的那一层向右平移的,因此 $f[i]=f[i-1]+b[i]+\text{max}_{j=0}^{i-1}b[j]$ ,边界条件 $f[0][0]=b[0]$.
时间复杂度 $O(n)$
我的解法:考虑从 $(j,j)$ 先横着走到 $(j,i)$ 再走到 $(i,i)$ 的过程,那么有:$f[i]=\text{max}_{j=0}^{i-1}(f[j]+\sum\limits_{k=j+1}^ib[k]+(i-j)·b[i])$.
前缀相减得 $f[i]=f[j]+sum[i]-sum[j]+(i-j)·b[j]$ .
移项得 $j·b[j]+sum[j]-f[j]=i·b[j]+sum[i]-f[i]$ .
容易发现可以斜率优化,要求截距得最大值,维护上凸壳.
但是这里的横坐标 $b[j]$ 不单调,因此无法使用单调数据结构维护,因此使用 CDQ 分治.
时间复杂度 $O(n\log n)$
不管了反正过去了...
#include < cstdio > #include < cstring > #include < algorithm > #define N 100010 using namespace std;
typedef long long ll;
ll a[N],
sum[N],
f[N];
int id[N],
t[N],
sta[N];
inline ll y(int i) {
return a[i] * i + sum[i] - f[i];
}
inline ll x(int i) {
return a[i];
}
inline long double slop(int a, int b) {
return (long double)(y(b) - y(a)) / (x(b) - x(a));
}
void solve(int l, int r) {
if (l == r) {
id[l] = l;
return;
}
int mid = (l + r) >> 1,
i,
j,
k;
solve(l, mid);
for (k = 0, i = l; i <= mid; i++) {
while (k && x(sta[k]) == x(id[i])) k--;
while (k > 1 && slop(sta[k], id[i]) <= slop(sta[k - 1], sta[k])) k--;
sta[++k] = id[i];
}
for (j = 1, i = mid + 1; i <= r; i++) {
while (j < k && slop(sta[j], sta[j + 1]) >= i) j++;
f[i] = min(f[i], f[sta[j]] + a[sta[j]] * (i - sta[j]) + sum[i] - sum[sta[j]]);
}
solve(mid + 1, r);
for (i = j = l, k = mid + 1; i <= r; i++) {
if (k > r || (j <= mid && (x(id[j]) == x(id[k]) ? y(id[j]) < y(id[k]) : x(id[j]) < x(id[k])))) t[i] = id[j++];
else t[i] = id[k++];
}
for (i = l; i <= r; i++) id[i] = t[i];
}
int main() {
int n,
i;
ll ans = 1ll << 62;
scanf("%d", &n);
for (i = n;~i; i--) scanf("%lld", &a[i]),
sum[i] = a[i];
for (i = 1; i <= n; i++) sum[i] += sum[i - 1];
memset(f, 0x3f, sizeof(f));
f[0] = a[0],
solve(0, n);
for (i = 0; i <= n; i++) ans = min(ans, 2 * f[i] + (4 * (n - i) - 1) * a[i]);
printf("%lld\n", ans);
return 0;
}
来源: http://www.bubuko.com/infodetail-2453860.html