[HDU 3507] Print Article【DP+斜率优化+单调队列】
Problem:
Time Limit: 9000/3000 MS (Java/Others)
Memory Limit: 131072/65536 K (Java/Others)
Problem Description
Zero has an old printer that doesn't work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.One day Zero want to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost
Now Zero want to know the minimum cost in order to arrange the article perfectly.
Input
There are many test cases. For each test case, There are two numbers N and M in the first line (0 ≤ n ≤ 500000, 0 ≤ M ≤ 1000). Then, there are N numbers in the next 2 to N + 1 lines. Input are terminated by EOF.
Output
A single number, meaning the mininum cost to print the article.
Sample Input
5 5 5 9 5 7 5
Sample Output
230
Author
Xnozero
Source
2010 ACM-ICPC Multi-University Training Contest（7）——Host by HIT
Recommend
zhengfeng | We have carefully selected several similar problems for you: 3506 3501 3504 3505 3498
Solution:
斜率优化 DP 的经典入门题。
令 dp[i] 为前 i 个单词最小总花费，S[i] 为单个花费的前缀和，则
- dp[ i ] = min{ dp[ j ] + ( S[ i ] - S[ j ] )2 + M }, 其中 0 ≤ j < i。
直接枚举 i, j 时间复杂度为 O(N2)，TLE。所以我们引入了斜率优化的概念。
首先证明决策单调，即若在状态 i 中，决策 k ( k > j) 较决策 j 更优，那么在 i 以后的状态 t 中，决策 k 总是较决策 j 更优，即
- 若有 dp[ k ] + ( S[ i ] - S[ k ] )2 + M ≤ dp[ j ] + ( S[ i ] - S[ j ] )2 + M …… (1)
- 则 dp[ k ] + ( S[ t ] - S[ k ] )2 + M ≤ dp[ j ] + ( S[ t ] - S[ j ] )2 + M …… (2)
- 证明如下：
- 由于 S[] 单调递增，可设 S[ t ] = S[ i ] + v，则有 v > 0。
- (2) 式 ⇐ dp[ k ] + ( S[ i ] + v - S[ k ] )2 + M ≤ dp[ j ] + ( S[ i ] + v - S[ j ] )2 + M
- ⇐ dp[ k ] + ( S[ i ] - S[ k ] )2 + 2v ( S[ i ] - S[ k ] ) ≤ dp[ j ] + ( S[ i ] - S[ j ] )2 + 2v ( S[ i ] - S[ j ] )
- ⇐ 2v ( S[ i ] - S[ k ] ) ≤ 2v ( S[ i ] - S[ j ] )
- ⇐ S[ k ] ≥ S[ j ] （显然成立）【证毕】
然后将两个决策点的比较式转化为斜率式：
- dp[ k ] + ( S[ i ] - S[ k ] )2 + M ≤ dp[ j ] + ( S[ i ] - S[ j ] )2 + M
- ⇒ dp[ k ] - 2 S[ i ] S[ k ] + S[ k ]2 ≤ dp[ j ] - 2 S[ i ] S[ j ] + S[ j ]2
- ⇒ dp[ k ] - dp[ j ] + S[ k ]2 - S[ j ]2 ≤ 2 S[ i ] ( S[ k ] - S[ j ] ) …… (3)
- ⇒ ( dp[ k ] - dp[ j ] + S[ k ]2 - S[ j ]2 ) / ( 2 S[ k ] - 2 S[ j ] ) ≤ S[ i ] …… (4)
(3)(4) 两式均可用来计算，前者有溢出风险，而后者有精度误差。。（自己看着办 QAQ）
由于 (4) 式中斜率 S[i] 单调递增，可以用单调队列维护一个斜率线段构成的下凸壳。
这样的话就 O(N) 啦 ~~ 然而我第一次交用 (4) 式计算 WA 了，改成 (3) 式就过了。。
Code: O(TN) [15308K, 390MS]
#include
#include
#include
#include
#include
#include
#define sqr(x) ((x) * (x))
using namespace std;
typedef long long ll;
int N, M;
ll C[500005], S[500005];
int q[500005], fr, re;
ll dp[500005];
inline ll dx(const int &j, const int &k) {return S[k] - S[j] << 1;}
inline ll dy(const int &j, const int &k) {return dp[k] - dp[j] + sqr(S[k]) - sqr(S[j]);}
int main(){
while(scanf("%d%d", &N, &M) != EOF){
for(register int i = 1; i <= N; i++)
scanf("%lld", C + i), S[i] = S[i - 1] + C[i];
fr = re = 0, q[re++] = 0;
for(register int i = 1; i <= N; i++){
while(fr + 1 < re && dy(q[fr], q[fr + 1]) <= dx(q[fr], q[fr + 1]) * S[i]) fr++;
dp[i] = dp[q[fr]] + sqr(S[i] - S[q[fr]]) + M;
while(fr + 1 < re && dy(q[re - 1], i) * dx(q[re - 2], q[re - 1]) <= dy(q[re - 2], q[re - 1]) * dx(q[re - 1], i)) re--;
q[re++] = i;
}
printf("%lld\n", dp[N]);
}
return 0;
}
发表评论