HDU4258_Covered Walkway

题目是一个很典型的斜率优化的题目。题意就不说了。

是这样的，对于双端优先队列，我们共有队首和队尾两个删除操作，来保证对于任意一个i，第一个元素都是最优的。

我们把dp的转移方程列出来就直达其状态为f[i]=min(f[j]+(a[i]-a[j+1])^2+m)。

所以我们如果有j1<j2且j2优于j1，那么一定有2*a[i]*(a[j2+1]-a[j1+1])>=f[j2]-f[j1]+a[j2+1]-a[j1+1]。同时由于等式两边都是正数而且随着i的增大，a[i]也是变大的，所以只要等式一旦成立，那么对于后面的每一个a[i]，都是成立的，所以此时说明j1这个元素已经没有用了，因为它一定不会是后面的最优解。所以可以从对首删除，这样我们就完成了对首的操作。

接下来稍微难一点的是队尾的的操作。是这样的，假如当前我们需要加入i这个元素，我们再加入前对队尾倒数第二个，倒数第一个和i分别进行比较，分别记为j1,j2,i。

显然一定存在一个 x1使得j2由于j1，也一定存在一个x2使得i由于j2，这样我们只要比较一下x1和x2的大小就知道该怎么操作了。

什么意思呢？如果存在x1>=x2，也就说还没等到j2由于j1，i就已经优于j2了，那么显然j2也是无用的应该从队尾删除。

然后加入当前的元素i。这样我们又一次保证了队列中间的单调性。

恩，就是这样的，上代码吧。。。代码效率很低，求大神指教。。。

#include <iostream>

#include <cstdio>

#include <cstring>

#define ll long long

#define maxn 1000100

using namespace std;

ll a[maxn],f[maxn],q[maxn];

ll n,m,head,tail;

ll xx,yy,xx1,yy1;

ll dy(ll j1,ll j2) { return f[j2]-f[j1]+a[j2+]*a[j2+]-a[j1+]*a[j1+]; }

ll dx(ll j1,ll j2) { return *(a[j2+]-a[j1+]); }

int main()

{

    while (scanf("%I64d%I64d",&n,&m) && (n|m))

    {

        for (int i=; i<=n; i++) scanf("%I64d",&a[i]);

        head=tail=,q[]=;

        for (int i=; i<=n; i++)

        {

            while (head<tail)

            {

                xx=dx(q[head],q[head+]);

                yy=dy(q[head],q[head+]);

                if (xx*a[i]>=yy) head++;

                    else break;

            }

            f[i]=f[q[head]]+(a[i]-a[q[head]+])*(a[i]-a[q[head]+])+m;

            while (head<tail)

            {

                xx=dx(q[tail-],q[tail]);

                yy=dy(q[tail-],q[tail]);

                xx1=dx(q[tail],i);

                yy1=dy(q[tail],i);

                if (yy*xx1>=yy1*xx) tail--;

                    else break;

            }

            q[++tail]=i;

        }

        printf("%I64d\n",f[n]);

    }

    return ;

}

巴特西

HDU4258_Covered Walkway

最新文章

热门文章