[2016北京集训测试赛3]masodik-[凸包]

Description

Soluton

666这道题竟然用凸包。。。

维护r和c的下凸壳。哪个斜率大走哪个。

证明：我们先不考虑其他的，只考虑两条路，如下图：

设图的长度为x，宽度为y。如果我们要走上面的路径，则r1*y+c1*x>=r2*y+c2*x。

移项得$\frac{(r1-r2)}{x}\geq \frac{(c2-c1)}{y}$。

显然对于只有两条路的情况，证明成立。

感性理解一下，最终的最优路径必然是由无数点的最优路径组成，如S->T1->T2->T3->T4。。。->T

所以，我就厚着脸皮认为它成立啦。

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int n,m;

int r[],c[],qr[],topr=,qc[],topc=;

int tpr,tpc;

long long ans;

int main()

{

    scanf("%d%d",&n,&m);

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

    {

        scanf("%d",&r[i]);

        while (topr>&&1ll*(r[i]-r[qr[topr]])*(qr[topr]-qr[topr-])<1ll*(r[qr[topr]]-r[qr[topr-]])*(i-qr[topr])) topr--;

        qr[++topr]=i;

    }

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

    {

        scanf("%d",&c[i]);

        while (topc>&&1ll*(c[i]-c[qc[topc]])*(qc[topc]-qc[topc-])<1ll*(c[qc[topc]]-c[qc[topc-]])*(i-qc[topc])) topc--;

        qc[++topc]=i;

    }

    tpr=tpc=;

    while (tpr<topr&&tpc<topc)

    {

        if (1ll*(r[qr[tpr+]]-r[qr[tpr]])*(qc[tpc+]-qc[tpc])<=1ll*(c[qc[tpc+]]-c[qc[tpc]])*(qr[tpr+]-qr[tpr]))

        ans+=1ll*(qr[tpr+]-qr[tpr])*c[qc[tpc]],tpr++;

        else ans+=1ll*(qc[tpc+]-qc[tpc])*r[qr[tpr]],tpc++;

    }

    if (tpr==topr) ans+=1ll*(m-qc[tpc])*r[n];else ans+=1ll*(n-qr[tpr])*c[m];

    cout<<ans;

}

巴特西

[2016北京集训测试赛3]masodik-[凸包]

Description

Soluton

Code

最新文章

热门文章