[HDU 3507] Print Article【DP+斜率优化+单调队列】

  • 2018-01-26
  • 0
  • 0

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

M is a const number.
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 &amp;j, const int &amp;k) {return S[k] - S[j] &lt;&lt; 1;}

inline ll dy(const int &amp;j, const int &amp;k) {return dp[k] - dp[j] + sqr(S[k]) - sqr(S[j]);}

int main(){
	while(scanf("%d%d", &amp;N, &amp;M) != EOF){
		for(register int i = 1; i &lt;= 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 &lt;= N; i++){
			while(fr + 1 &lt; re &amp;&amp; dy(q[fr], q[fr + 1]) &lt;= dx(q[fr], q[fr + 1]) * S[i]) fr++;
			dp[i] = dp[q[fr]] + sqr(S[i] - S[q[fr]]) + M;
			while(fr + 1 &lt; re &amp;&amp; dy(q[re - 1], i) * dx(q[re - 2], q[re - 1]) &lt;= dy(q[re - 2], q[re - 1]) * dx(q[re - 1], i)) re--;
			q[re++] = i;
		}
		printf("%lld\n", dp[N]);
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai