首页 > 代码库 > bzoj 3437 斜率优化DP

bzoj 3437 斜率优化DP

2024-07-03 12:16:59   222人阅读

　　写题解之前首先要感谢妹子。

　　比较容易的斜率DP，设sum[i]=Σb[j]，sum_[i]=Σb[j]*j，w[i]为第i个建立，前i个的代价。

　　那么就可以转移了。

　　备注：还是要感谢妹子。

/**************************************************************
    Problem: 3437
    User: BLADEVIL
    Language: C++
    Result: Accepted
    Time:3404 ms
    Memory:39872 kb
****************************************************************/
 
//By BLADEVIL
#include <cstdio>
#define maxn 1000010
#define LL long long
 
using namespace std;
 
LL n;
LL a[maxn],sum[maxn],sum_[maxn];
LL que[maxn];
LL w[maxn];
 
LL get(LL i) {
    return (w[i]+sum_[i]);
}
 
int main() {
    scanf("%lld",&n);
    for (LL i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (LL i=1;i<=n;i++) scanf("%lld",&sum[i]);
    for (LL i=1;i<=n;i++) sum_[i]=i*sum[i];
    for (LL i=1;i<=n;i++) sum[i]+=sum[i-1],sum_[i]+=sum_[i-1];
    LL h(1),t(1);
    for (LL i=1;i<=n;i++) {
        while ((t-h>0)&&((sum[que[h]]-sum[que[h+1]])*i<=(w[que[h]]+sum_[que[h]]-w[que[h+1]]-sum_[que[h+1]]))) h++;
        w[i]=w[que[h]]+(sum[i]-sum[que[h]])*i-(sum_[i]-sum_[que[h]])+a[i];
        //w[i]=w[que[h]]+sum_[que[h]]-i*sum[que[h]]+i*sum[i]+a[i]-sum_[i];
        while ((t>h)&&((get(que[t-1])-get(i))*(sum[que[t-1]]-sum[que[t]])<=(get(que[t-1])-get(que[t]))*(sum[que[t-1]]-sum[i]))) t--;
        /*
        while ((t-h>0)&&(
        (w[que[t-1]]+sum_[que[t-1]]-w[i]-sum_[i])*(sum[que[t-1]]-sum[que[t]])<=
                         (w[que[t-1]]+sum_[que[t-1]]-w[que[t]]-sum_[que[t]])*(sum[que[t-1]]-sum[i]))
        ) t--;
        */
        que[++t]=i;
    }
    printf("%lld\n",w[n]);
    return 0;
}

 


联系
我们