DP优化 get ！

A4paper · 2018-10-02 15:13:22 · 个人记录

单调队列、优先队列、堆优化DP：

传送门

普通的方程是很好写的：

对于优化，由于题目要求最大值，所以只需要将 (i-r ≤ j ≤ i-l) 范围内的值排序并每次输出最大值即可，

我用的堆维护，记得将超出 (i-r ≤ j ≤ i-l) 范围的值 pop 掉。

int n,l,r,ans,tot;
int point;
priority_queue <PII,vector<PII> >que;

int main(void)
{
    cin >> n >> l >> r;
    n++;
    for(int i=1;i<=n;i++)   cin >> a[i];
    for(int i=l+1;i<=n;i++)
    {
        que.push(make_pair(f[i-l],i-l));
        while(!que.empty() && que.top().second<i-r) que.pop();
        f[i] = que.top().first+a[i];
    }
    for(int i=n-r;i<=n;i++)
        ans = max(ans,f[i]);
    cout << ans;
    return 0;
}

提高：

传送门

这道也是优先队列优化，但不好调。

首先，当前行的状态与上一行有关，所以将上一行的元素依次扔到队列里，

然后移动当前行的 j 同时将上一行的新的满足条件的元素扔入，不满足的踢出，

由于此行只与上一行有关，所以要开 n-1 个优先队列，或者在一行结束后将队列清空

struct node{
    int x,y,v;
    bool operator <(node a) const {
        return v < a.v;
    }
}point[MAXN];

int main(void)
{
    cin >> n >> m >> k >> t;
    for(int i=1;i<=k;i++)
    {
        cin >> point[i].x >> point[i].y >> point[i].v;
        f[point[i].x][point[i].y] = point[i].v;
    }
    for(int i=1;i<=n;i++)
    {
        priority_queue <node,vector<node> >que;
        for(int j=1;j<=t;j++)
        {
            que.push((node){i,j,f[i][j]});
        }
        for(int j=1;j<=m;j++)
        {
            if(j+t <= m) que.push((node){i,j+t,f[i][j+t]});
            while(que.top().y<max(0,j-t) && !que.empty()) que.pop();
            if(!que.empty()) f[i+1][j] += que.top().v;
        }
    }
    for(int i=1;i<=m;i++)
    {
        ans = max(ans,f[n][i]);
    }
    cout << ans;
    return 0;
}

双端队列：

传送门

其实就是单调队列，再加上二分答案，其实还是很好想的

不过就是很欣赏这种入队方式，大大减少了对边界条件的判断，降低了思维复杂度。

这种入队方式总的来说就是枚举每个点 i ，再枚举一个 j ，如果 i\ j 间的距离大于 \_R ，则入队，再枚举队首元素将大于 _L 的元素丢出去。（\_L\ \ \_R 表示能转移到 i 点的区间的左右端点）

bool check(int mid)
{
    memset(f,0,sizeof f);
    deque <int>q;
    int _R = max(d-mid,(int)1);
    int _L = d+mid;
    int j=0;
    for(int i=1;i<=n;i++)
    {
        for(;j<i && len[i]-len[j]>=_R;j++)
        {
            while(!q.empty() && f[j]>=f[q.back()])
                q.pop_back();
            q.push_back(j);
        }
        while(!q.empty() && len[i]-len[q.front()]>_L)
            q.pop_front();
        if(!q.empty()) f[i] = f[q.front()]+val[i];
        else f[i] = 0x8080808080808080;
        if(f[i] >= k) return 1;
    }
    return 0;
}

signed main(void)
{
    cin >> n >> d >> k;
    for(int i=1;i<=n;i++)
        cin >> len[i] >> val[i];
    R = 1005;
    while(L <= R)
    {
        int mid = (L+R)>>1;
        if(check(mid)) 
        {
            ans = mid;
            R = mid-1;
        }
        else L = mid+1;
    }
    cout << ans;
    return 0;
}