Time Limit: 10 Sec Memory Limit: 512 MB
Description
Input
第一行为一个整数N表示战线的总长度。 第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。
Output
共一个整数，表示最小的战线花费值。
HINT
1
<
=
N
<
=
1
0
6
,
1
<
=
A
i
<
=
1
0
9
1<=N<=10^6,1<=Ai<=10^9
1<=N<=106,1<=Ai<=109
题目分析
d
p
[
i
]
dp[i]
dp[i]表示前
i
i
i个检查点都能通过，且第
i
i
i个检查点放防御塔所需最小费用 首先有
O
(
n
2
)
O(n^2)
O(n2)的方程
d
p
[
i
]
=
d
p
[
j
]
+
(
i
−
j
−
1
)
(
i
−
j
)
/
2
+
a
i
[
i
]
dp[i]=dp[j]+(i-j-1)(i-j)/2+ai[i]
dp[i]=dp[j]+(i−j−1)(i−j)/2+ai[i]即
j
+
1
j+1
j+1~
i
i
i都放木偶
展开再移项
d
p
[
j
]
+
1
2
∗
(
j
2
+
j
)
=
i
∗
j
−
1
2
∗
(
i
2
−
i
)
−
a
i
[
i
]
+
d
p
[
i
]
dp[j]+\frac{1}{2}*(j^2+j)=i*j-\frac{1}{2}*(i^2-i)-ai[i]+dp[i]
dp[j]+21∗(j2+j)=i∗j−21∗(i2−i)−ai[i]+dp[i] 即
d
p
[
j
]
+
1
2
∗
(
j
2
+
j
)
dp[j]+\frac{1}{2}*(j^2+j)
dp[j]+21∗(j2+j)为
y
y
y，
j
j
j为
x
x
x，
i
i
i为斜率进行斜率优化
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std
;
typedef long long lt
;
typedef double dd
;
#define sqr(x) ((x)*(x))
lt
read()
{
lt f
=1,x
=0;
char ss
=getchar();
while(ss
<'0'||ss
>'9'){if(ss
=='-')f
=-1;ss
=getchar();}
while(ss
>='0'&&ss
<='9'){x
=x
*10+ss
-'0';ss
=getchar();}
return f
*x
;
}
const int maxn
=2000010;
int n
;
lt ai
[maxn
],dp
[maxn
];
int q
[maxn
],ll
,rr
;
lt
qans(lt i
,lt j
){ return dp
[j
]+(sqr(j
)+j
+sqr(i
)-i
)/2-i
*j
+ai
[i
];}
dd
calc(lt j1
,lt j2
)
{
lt ty
=(dp
[j2
]+(sqr(j2
)+j2
)/2)-(dp
[j1
]+(sqr(j1
)+j1
)/2);
lt tx
=j2
-j1
;
return (dd
)ty
/(dd
)tx
;
}
int main()
{
n
=read();
for(int i
=1;i
<=n
;++i
) ai
[i
]=read();
ll
=rr
=1;
for(int i
=1;i
<=n
;++i
)
{
while( ll
<rr
&& calc(q
[ll
],q
[ll
+1])<=i
) ++ll
;
dp
[i
]=qans(i
,q
[ll
]);
while( ll
<rr
&& calc(q
[rr
-1],q
[rr
])>=calc(q
[rr
],i
)) --rr
;
q
[++rr
]=i
;
}
printf("%lld",dp
[n
]);
return 0;
}
