Brief description :
给定两个字符串，要求一个分组方案使得不相似度尽可能少，不相似度定义为分的段数*m，然后每一段不相似度求和后再平方…
…
Analyse :
经常会遇到这样的分组类DP题，其每一组的值先求和后再进行计算，且所有的值同号（都是正数或都是负数），N的范围很大，用O（N^2）的DP会TLE，此时，一种很重要的优化是：斜率优化。
/*
Author : xiaodao
Prob : RQnoj 418. 浪浪的小爱好
Status : TLE (60)
Last modify : ...
*/
#include <iostream>
using namespace std;
const long long INF = (long long)(1) << 60;
const int N = 200001;
long long dp[N], s[N];
int n, m;
void init(){
cin >> n >> m;
string a, b; cin >> a >> b;
for (int i=1;i<=n;i++){
s[i] = s[i-1] + abs(int(a[i-1]-b[i-1]));
}
}
void solve(){
for (int i=1;i<=n;i++){
dp[i] = INF;
for (int j=0;j<i;j++)
dp[i] = min(dp[i], dp[j] + (s[i]-s[j])*(s[i]-s[j]) + m);
}
}
int main(){
init(); solve();
cout << dp[n]-m << endl;
}
/*
Author : xiaodao
Prob : RQnoj 418. 浪浪的小爱好
Status : Accepted
Last modify : ..
*/
#include <iostream>
using namespace std;
const double INF = 1e10;
const int N = 200001;
long long dp[N], s[N];
int n, m;
double h(int j1, int j2){
if (s[j2] - s[j1] == 0) return INF;
return (dp[j2] - dp[j1])/(s[j2] - s[j1]) + s[j1] + s[j2];
}
void init(){
cin >> n >> m;
string a, b; cin >> a >> b;
for (int i=1;i<=n;i++){
s[i] = s[i-1] + abs(int(a[i-1]-b[i-1]));
}
}
void solve(){
int Q[N] = {0}, L = 0, R = 0;
for (int i=1;i<=n;i++){
while ( L < R && h(Q[L], Q[L+1]) < 2 * s[i]) L++;
dp[i] = dp[Q[L]] + (s[i]-s[Q[L]]) * (s[i]-s[Q[L]]) + m;
while ( L < R && h(Q[R-1], Q[R]) >= h(Q[R] ,i) ) R--;
Q[++R] = i;
}
}
int main(){
init(); solve();
cout << dp[n] - m << endl;
}
/*
Author : xiaodao
Prob : RQnoj 418. 浪浪的小爱好
Status : Accepted
Last modify : ...
*/
#include <iostream>
using namespace std;
const int INF = 1000000000;
const int N = 200001;
long long dp[N], s[N];
int n, m;
int H(int i, int j){
return dp[i] - dp[j] + s[i]*s[i] - s[j]*s[j];
}
void init(){
cin >> n >> m;
string a, b; cin >> a >> b;
for (int i=1;i<=n;i++){
s[i] = s[i-1] + abs(int(a[i-1]-b[i-1]));
}
}
void solve(){
int Q[N] = {0}, L = 0, R = 0;
for (int i=1;i<=n;i++){
while ( L < R && H(Q[L], Q[L+1])>=s[i]*2*(s[Q[L]]-s[Q[L+1]]) ) L++;
dp[i] = dp[Q[L]] + (s[i]-s[Q[L]])*(s[i]-s[Q[L]]) + m;
while ( L < R && H(Q[R-1], Q[R])*(s[Q[R]]-s[i])>=H(Q[R], i)*(s[Q[R-1]]-s[Q[R]]) ) R--;
Q[++R] = i;
}
}
int main(){
init(); solve();
cout << dp[n]-m << endl;
}
dp[i] 表示考察前i个字符，分段后形成的最小代价。
\[dp[i] = min\{dp[j] + (s[i]-s[j])^2\} + m \ |\ 0\leq j
下面的步骤时考察枚举时的前后两组变量 j1, j2，j1 < j2 且决策 j1 比 j2 更优，据此列出不等式，并对其进行移项、变号（注意到 s 数组一定单调递增的特性，s[j1] - s[j2] < 0 ）等操作，直到不等式中所有的已知量都被移到不等号同一边（一般是右边）为止。
\[dp[j_1] + (s[i]-s[j_1])^2 + m< dp[j_2] + (s[i]-s[j_2])^2 + m\]
\[dp[j_1] - dp[j_2] + s[j_1]^2 - s[j_2]^2 < 2s[i]s[j_1] - 2s[i]s[j_2]\]
使用平方差公式
\[dp[j_1] - dp[j_2] + (s[j_1] + s[j_2])(s[j_1] - s[j_2]) < 2s[i](s[j_1] - s[j_2])\]
除过来 ...
\[\frac{dp[j_2] - dp[j_1]}{s[j_2] - s[j_1]} + s[j_2] + s[j_1] > 2s[i]\]
我们发现左边的式子已经同 i 无关，制作辅助函数,
\[h(j_1, j_2) = \frac{dp[j_2] – dp[j_1]}{s[j_2] – s[j_1]} + s[j_2] + s[j_1]\]
于是当决策 j1 优于决策当且仅当 $$h(j_1, j_2) > 2s[i]$$ …
为了要可以应用单调队列，接下来要挖掘 h 函数的一个重要性质，考察前后一组决策变量，j1 < j2 < j3，且满足 $$h(j_1, j_2) \geq h(j_2, j_3)$$
那么分类讨论以后可以肯定， j2一定不会是最优的决策。
1: h(j1, j2) > s[i] … 立即可得 j1 优于 j2。
2: h(j1, j2) <= s[i] ，那么此时， 因为 h(j2, j3) 比 h(j1, j2) 还要小，因此 j2 比 j3 劣。
（ h(j2, j3) <= h(j1, j2) <= s[i] ）
因此，用单调队列保存一组相邻状态间 h 函数递减的决策。（啊，是递增晕了我已经。～）
... 且最优方案一定在最左边。＃（刚好和前面的一个性质组合起来用... ）
External link :
http://www.rqnoj.cn/Problem_418.html
http://hi.baidu.com/matobeatjollwish/blog/item/b30fea355aa3c4365bb5f509.html ( 失效
http://www.csie.ntnu.edu.tw/~u91029/WordWrap.html
