[COCI2010-2011#5] DVONIZ（加强版）

_H17_ · 2023-10-01 15:58:53 · 题解

题目分析

首先分析下数据，n \le 3 \times 10^6 基本上肯定是 O(n \log n) 的复杂度或 O(n)。

看见 \log 难道不会想起二分答案吗？

不过看着这种输出大概又像是 DP，所以大概就是向 LIS 那样借助二分进行 DP。

状态不说了，输出格式替你设好了。

对于 f_i 肯定可以从 f_{i-1} 去掉首尾得到，所以得到状态转移方程 f_i=\max(f_i,f_{i-1}-2)。

代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,m,a[3000001],l,r,mid,f[3000001];
bool check(int x,int y){
    return a[x]-a[x-y]<=m&&a[x+y]-a[x]<=m;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]+=a[i-1];
    }
    for(int i=1;i<=n;i++){
        l=0,r=min(i,n-i);
        while(l<r){
            mid=l+r+1>>1;
            if(check(i,mid))
                l=mid;
            else
                r=mid-1;
        }
        f[i-l+1]=max(f[i-l+1],2*l);
    }
    for(int i=1;i<=n;i++)
        f[i]=max(f[i],f[i-1]-2);
    for(int i=1;i<=n;i++)
        cout<<f[i]<<'\n';
    return 0;
}

弱化版&双倍经验

题目、题解。