斜率dp

第二道斜率dp问题，不会做。。。。。
真是太狼狈了！！！但是也加深了对斜率dp的理解

这一题，我上来就用动态规划求出了任意两仓库之间所产生的贡献度，很快啊！！！
假设我们用f[i][j]来表示从仓库i到仓库j连续的这一段所产生的贡献度。
f[i][j] = f[i][j-1]+(sum[j-1]-sum[i-1])*a[j]
但是，当我进行dp时却傻眼了！！！
我的状态定义为：dp[i][j]
指到i为止，使用了j个***答案。
而dp转移方程就是dp[i][j] = min(dp[k][j-1]+f[k+1][i])
我怎么可能对这个式子进行斜率dp啊
dp[i][j] = dp[k][j-1]+f[k+1][i]

因为我的状态定义是二维的，所以，我是一定要把一维看作是常数的。
但是，我们却发现在这个式子中，k与两个维数都想关联了。
也就是说，这个式子中我们把谁看作是斜率，把谁看作是点呢？
若我们把维数i放在外面，那么我们就可以把i看作是常数。
那么在更新j这一维数时，是不用在意的。
那么我们想想，什么是斜率？dp[k][j-1]？怎么可能有k
那么斜率是个定值？1？
那么点就是(dp[k][j-1],-f[k+1][i])?
看似可以，实则放屁。
注意力哈，我们发现这个点中有j，而j正式我们更新的维度！
这就很糟糕了！！在我们维护的这一凸包中，点竟然是不断变化的！很明显不可能！
于是，我不会做了。

那么我究竟是在哪一步出错了呢？
状态的定义并没有错，但是状态转移方程写错了。
我们应该写一个更好的状态转移方程，能够使用斜率dp的状态转移方程。
dp[i][j] = dp[k][j-1] + f[k+1][i]
坏事就坏事在f[k+1][i] 他把k和i直接建立关联了。
我们不能这样求
不妨这样求，f[i]为1到i这一连续区间的贡献度，
然后我们就知道了上面，k+1到i区间的贡献度其实是可以这样算的
f[i]-f[k]-sum[k](sum[i]-sum[k])
然后我们的状态转移方程就是
dp[i][j] = dp[k][j-1] + f[i]-f[k]+sum[k](sum[i]-sum[k])
这个方程是符合斜率优化的性质的！！！！！！！
真是太巧妙了！！！
我们在这里把j看作是常数，把i放在内循环，为什么这样呢？
因为dp[k][j-1]我们可以看到k是和j绑定在一起的，所以如果优先更新j的话
那么就会出“动点”问题！！！
所以优先更新i
而这是一个二维dp，我们的斜率优化其实是作用在一个维度上的，所以对于每一个j我们都要有一个队列去优化！！！
另外这里i,j,k其实还是有范围的！！一定要注意范围！并且dp也是有初始态的，
另外在队列中放置第一个元素也要好好斟酌！！！！

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
typedef long long ll;
int n,m;
ll f[1100];
ll dp[1100][1100];
ll a[1100];
ll sum[1100];
deque<int> que;
bool check(int j,ll k){
    int a = que[0],b=que[1];
    ll x1 = sum[a],y1 = dp[a][j-1]-f[a]+sum[a]*sum[a];
    ll x2 = sum[b],y2 = dp[b][j-1]-f[b]+sum[b]*sum[b];
    if (x1<x2)swap(x1,x2),swap(y1,y2);
    return y1-y2<=k*(x1-x2);
}
bool check2(int j,int i){
    int a=que[que.size()-1],b=que[que.size()-2];
    ll x1 = sum[a],y1 = dp[a][j-1]-f[a]+sum[a]*sum[a];
    ll x2 = sum[b],y2 = dp[b][j-1]-f[b]+sum[b]*sum[b];
    ll x3 = sum[i],y3 = dp[i][j-1]-f[i]+sum[i]*sum[i];
    if ((x3-x2)*(x1-x2)<0)swap(x1,x2),swap(y1,y2);
    return (x1-x2)*(y3-y2)<=(x3-x2)*(y1-y2);
}
int main(){
    while (scanf("%d %d",&n,&m)){
        if (n==0&&m==0)break;
        for (int i=1;i<=n;++i)scanf("%lld",&a[i]);
        for (int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i];
        for (int i=1;i<=n;++i)f[i] = f[i-1]+sum[i-1]*a[i];
        for (int i=1;i<=n;++i)dp[i][0] = f[i];
        for (int j=1;j<=m;++j){
            que.clear();que.push_back(j);
            for (int i=j+1;i<=n;++i){
                ll k = sum[i];
                while (!que.empty()&&que.front()<j)que.pop_front();
                while (que.size()>=2&&check(j,k))que.pop_front();
                int o = que.front();
                dp[i][j] = dp[o][j-1]+f[i]-f[o]-sum[o]*(sum[i]-sum[o]);
                while (que.size()>=2&&check2(j,i))que.pop_back();
                que.push_back(i);
            }
        }
        printf("%lld\n",dp[n][m]);
    }
}

在写出斜率dp的方程时，我们一定要保证斜率dp中至少有一维与我们目前选择的点不绑定！！

Lawrence

斜率dp