修长廊 | BigHead

题意

现在要修长廊覆盖n个点，第i个点可以单独修一个长廊，也可以修到前面第j个点（覆盖j到i之间的点），现在修i和j之间的长廊花费cost(i,j) = W + (x $ _i － x _j ) ^{2} ,其中W是固有花费,现在求最小花费是多少 $

分析
我们状态很好建立,dp[i]表示覆盖到第i个点为止至少需要花费多少,但是他可以有很多状态转移过来.
```
  dp[i] = min(dp[j-1]+cost(j,i));
```
如果现在有两个状态j和k(其中j>k)可以转移过来.那么用单调队列dp思想把这两个相减
```
     dp[j] + cost(j,i) - dp[k] - cost(k,i) 
      
   =(dp[j] +x[j]*x[j])-(dp[k]+ x[k]*x[k]) -　2*x[i]*(x[j]-x[k]) 
  
```
那么也就是说如果dp[j]转移过来比dp[k]更优的话,就有上式小于 0,那么我们在更新最优的dp[y]的时候,如果前面存在一个状态x比状态i差,那么便有上式成立

同时可以发现如果现在就已经成立,那么这个式子对y以后的状态都会成立,因为对y以后的xi上式也成立(这个就是斜率dp的特点,总会有一个自变量一直递增或递减),那么状态x就属于无用状态应该从队列中剔除

判定条件一:如果i点没有j点优(也就是说j点比i点更优)的条件是i和j(i<j)斜率小于2x[i]
那么如何保证队列起第一个就是最优的呢?
- 感性的认识:
  - 根据上面的式子我们可以一直判断第一个和第二个元素然后剔除,从而使得保证队队列第一个一定比第二个更优,那么剩下的就需要保证第一个比第三个,第一个比第四个更优…这个性质一直成立就好了
  - 假设上面这个性质成立则有:23点的斜率大于12点,34点斜率大于12点…
但是确保每相邻两个点斜率大于12点不具有传递性,所以我们可以缩小简化:23点的斜率大于12点,34点斜率大于23点…从而形成了下凸包
```
  *    从结果看:斜率递增保证了下凸包,而下凸包其实是保证了**:第三个点没有第二个点优,第四个点没有三个点优..**,因为第一个破坏下凸包性质的点一定不是最优,可参考理性认识的证明
  
  
```
所以我们要维护上面两个性质:1:第一个点比第二个点优,2:第三个点没有第二个点优,第四个点没有三个点优… (用维护斜率递增实现)

思考

如何证明维护的队列的第一个就是最优的呢?
- 理性认识:

$    dp[i] = dp[j] + x[j]  ^{2}  + x[i] ^{2} +　2x[i]*x[j] + W $
    
$    dp[i] - W - x[i] ^{2}  = dp[j] + x[j]  ^{2} +　2x[i]*x[j] $

    从上面这个式子看出dp[i] , $x[i] ^{2} ,$ Ｗ这三个相对于i是定值
    
-    **问题转换:**  我们要找到这样一个 x[j] 和 $dp[j] + x[j] ^{2} $使得 dp[i] 最小,看成b = y - kx,也就是b最小.从而我们可以画出一些点$(2*x[j],dp[j] + x[j] ^{2} )$,用斜率固定k的直线从下面往上面开始扫描,第一个接触到的点就是我们要找的最优点.这样找的话就会发现一个特点,上凸包的转折点永远不会被扫到,所以也应该剔除.

    如果我们在每一次插入的时候一直这样判断,那么就能够保证最后两个斜率一定大于前两个点的斜率,由于插入斜率大小具有**传递性**,所以能够保证**斜率递增**
    
    **但是光斜率递增就一定能够使得第一个最优吗?**
    
    -    确保第一个最优的充分必要条件是每个点和第一个点的斜率大于等于2x[i],这样看来显然不能够确保第一个最优.(**举一个极限的例子,所有点和第一个点的斜率都小于2x[i]但是却递增**)
    
-    为了**弥补**上面的不足,可以让第一个优于第二个,也就是12斜率大于2x[i],由于上面凸包的性质使得第一个点和所有点斜率都大于2x[i]也就是说,以后的点不能够比第一个点更优.所以:**第一个是最优的**

/*************************************************************************
	> File Name: b.cpp
	> Author: liangxianfeng
	> Mail:   641587852@qq.com
	> Created Time: 2016年05月13日 星期五 16时20分14秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
#define ll long long
#define rep(i,n) for(int i =0; i < n; ++i)
#define CLR(x) memset(x,0,sizeof x)
#define MEM(a,b) memset(a,b,sizeof a)
#define pr(x) cout << #x << " = " << x << " ";
#define prln(x) cout << #x << " = " << x <<  endl; 
const int maxn = 4e5+100;
const int INF = 0x3f3f3f3f;

struct Node{
    ll num, x;
    Node (){}
    Node(ll _num, ll _x){
        num = _num;
        x = _x;
    }
}q[maxn];
ll dp[maxn];
ll x[maxn];
bool get(const Node& a, const Node &b, const ll& x){
    return b.num - a.num <= x*(b.x-a.x)*2;
}
bool get2(const Node& a, const Node& b, const Node& c){
    return (b.num - a.num)*(c.x - a.x) >= (c.num - a.num)*(b.x - a.x);
}
int main(){
#ifdef LOCAL
	freopen("/home/zeroxf/桌面/in.txt","r",stdin);
	//freopen("/home/zeroxf/桌面/out.txt","w",stdout);
#endif
    int t;
    scanf("%d", &t);
    while(t--){
        ll w;
        int n;
        scanf("%d%lld", &n, &w);
        for(int i = 1; i <= n; ++i){
            scanf("%lld", &x[i]);
        }
        int tail = -1,head = 0;
        dp[0] = 0;
        dp[1] = w;
        q[++tail] = Node(x[1]*x[1], x[1]);
        q[++tail] = Node(w+x[2]*x[2],x[2]);
        for(int i = 2; i <= n; ++i){
            while(head < tail && get(q[head], q[head+1], x[i])) head++;
            dp[i] = q[head].num + w + (x[i]*x[i]) - 2*x[i]*q[head].x;
            dp[i] = min(dp[i], dp[i-1] + w);
            Node qnum = Node(dp[i] + (x[i+1]*x[i+1]), x[i+1]);
            while(head < tail && get2(q[tail-1], q[tail], qnum)) tail--;
            q[++tail] = qnum;

        }
        printf("%lld\n", dp[n]);
    }
	return 0;
}

题意

分析

思考