DP训练——线段树优化DP

作者: 云中翻月 | 来源:发表于2020-02-25 11:42 被阅读0次

线段树优化DP

HDU3698
题意
给定 $n*m(n<=100,m<=5000)$ 的矩阵 $t$ 和 $f$ ，须从 $t$ 矩阵的每行选择一个数字，使得数字和最小。
选择时须保证前后选择的两个数字 $(i,j)$ 和 $(i+1,k)$ ，满足 $|j-k|≤f(i,j)+f(i+1,k)$ 。
题解
状态定义： $d[i,j]$ 表示到第 $i$ 行，当前行选第 $j$ 列的最小花费。
边界： $d[1,i]=t[1,i],1<=i<=m$
目标： $min{d[n,i]},1<=i<=m$
转移方程： $d[i][j]=min{d[i−1][k]}+t[i][j](|j−k|≤f(i,j)+f(i+1,k))$
目前的时间复杂度为 $O(n*m^2)$ 。
我们考虑优化转移条件，将绝对值不等式打开，会发现
$j-f[i][j]<=k+f[i+1][k],j>=k$
$k-f[i+1][k]<=j+f[i][j],j<k$
将k和j的关系在数轴上画出来，会发现 $k∈[j-f[i,j],j+f[i,j]]$ 。
因此，我们可以每行用一个线段树来维护这个区间上的最小值，通过懒惰标记进行区间修改和查询即可。
优化后的时间复杂度为 $O(n*mlogm)$ 。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int maxm=5000+5;
const int INF=0x3f3f3f3f;
int n,m,t[maxn][maxm],f[maxn][maxm];
int d[maxn][maxm];
struct SegmentTree{
    int l,r,dat,tag;
}tr[maxm<<2];
int ans;
void init(){
    ans=INF;
    // memset(t,0,sizeof(t));
    // memset(f,0,sizeof(f));
    // memset(d,INF,sizeof(d));
}
void build(int rt,int l,int r){
    tr[rt].l=l,tr[rt].r=r;
    if(l==r){
        tr[rt].dat=INF;
        tr[rt].tag=INF; //INF表示没有标记
        return;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
    tr[rt].dat=min(tr[rt<<1].dat,tr[rt<<1|1].dat);
    tr[rt].tag=min(tr[rt<<1].tag,tr[rt<<1|1].tag);
}
void spread(int rt){
    if(tr[rt].tag!=INF){
        tr[rt<<1].dat=min(tr[rt<<1].dat,tr[rt].tag);
        tr[rt<<1|1].dat=min(tr[rt<<1|1].dat,tr[rt].tag);
        tr[rt<<1].tag=min(tr[rt<<1].tag,tr[rt].tag);
        tr[rt<<1|1].tag=min(tr[rt<<1|1].tag,tr[rt].tag);
        tr[rt].tag=INF;
    }
}
void update(int rt,int l,int r,int val){
    if(tr[rt].l>=l&&tr[rt].r<=r){
        tr[rt].dat=min(tr[rt].dat,val);
        tr[rt].tag=min(tr[rt].tag,val);
        return;
    }
    spread(rt);
    int mid=tr[rt].l+tr[rt].r>>1;
    if(l<=mid) update(rt<<1,l,r,val);
    if(r>mid) update(rt<<1|1,l,r,val);
    tr[rt].dat=min(tr[rt<<1].dat,tr[rt<<1|1].dat);
}
int ask(int rt,int l,int r){
    if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].dat;
    spread(rt);
    int mid=tr[rt].l+tr[rt].r>>1;
    int res=INF;
    if(l<=mid) res=min(res,ask(rt<<1,l,r));
    if(r>mid) res=min(res,ask(rt<<1|1,l,r));
    return res;
}
void dp(){
    for(int i=1;i<=m;i++) d[1][i]=t[1][i];
    for(int i=2;i<=n;i++){
        build(1,1,m);
//        for(int j=1;j<=m;j++) D(f[i-1][j]);
//        E;
        for(int j=1;j<=m;j++) update(1,j-f[i-1][j],j+f[i-1][j],d[i-1][j]);
        for(int j=1;j<=m;j++){
            int temp=ask(1,j-f[i][j],j+f[i][j]); 
//          D(temp);E; 
            d[i][j]=temp+t[i][j];
        } 
//        for(int j=1;j<=m;j++) cout<<d[i][j]<<" ";
//        E;
        /*
        9 5 3 8 7
        8 2 6 8 9
        1 9 7 8 6
        0 1 0 1 2
        1 0 2 1 1
        0 2 1 0 2
        */
    }
    for(int i=1;i<=m;i++) ans=min(ans,d[n][i]);
    printf("%d\n",ans);
}
int main() {
    ios::sync_with_stdio(false);
//  freopen("HDU3698.in","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        if(!n&&!m) break;
        init();
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&t[i][j]);
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&f[i][j]);
        /* 
        cout<<endl<<"-------"<<endl;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cout<<t[i][j]<<" ";
            }
            cout<<endl;
        }
        cout<<endl<<"-------"<<endl;
        */ 
        dp();
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

HDU4719
题意
$n(n<=1e5)$ 个数排成一行，可以将其分为若干组，每组长度不大于给定常数 $L$ 。
设第i组的最后一个数字为 $b_i$ ，则分组时需保证 $b_i>b_{i-1}$ ，同时对应贡献为 $b_{i}^{2}-b_{i-1}$ 。
求贡献和的最大值。
题解
首先考虑朴素dp。
状态定义： $f[i]$ 表示处理好前 $i$ 个人，并且以 $i$ 结尾的最大分数。
边界： $f[0]=0$ ,其他为 $-INF$
目标： $f[n]$
转移方程： $f[i]=max{f[j]+a[i]*a[i]-a[j]},a[i]>a[j]且i-L<=j<=i-1$
分离变量后，转移方程变化为 $f[i]=max{f[j]-a[j]}+a[i]*a[i],a[i]>a[j]且i-L<=j<=i-1$
即需要用线段树，高效求解 $[i-L,i-1]$ 区间上 $f[j]-a[j]$ 的最大值。
这时遇到一个问题，即如何保证 $[i-L,i-1]$ 区间上的 $a$ 值都比 $a[i]$ 小。
这样相当于线段树有两个关键字 $b$ 和 $f$ ，在满足第一关键字比 $b$ 小的情况下，找一个 $f$ 最大的。
这样其实是有一个套路的，既然反正只有第一关键字满足条件的能更新，那就干脆按照第一关键字排序。
其实，对于每个士兵，我们可以先按照身高来进行升序排列，如果身高相同，我们就按照编号（原来的顺序）降序排列，
然后对于排序后的士兵 $i$ ，我们设他原来的编号为 $idx_i$ ，则我们就查找线段树上 $[idx_i−L,idx_i−1]$ 的价值，同时更新也是更新线段树上的 $idx_i$ 的位置。
因为对于每个士兵 $i$ ，如果在排序前能找到和他进行状态转移的士兵 $j$ ，那么排序后，肯定有 $idx_j∈[idx_i−L,idx_i−1]$ 。
还有一种更通俗的解释：
这题需要从小的开始处理，因为小的不受大的影响，所以先处理没关系。
但是如果遇到有相同的高度的点 $j$ ， $i$ 时，我们需要先处理排在后面的 $i$ 。
因为如果先处理前面的 $j$ ，而且很不巧刚好j有最大值，那么处理i的时候就会查到那个值，但是这其实是非法的。
反之我们先处理后面的 $i$ ，此时 $j$ 没有插入到线段树上，所以 $i$ 不受影响。
而处理前面的j的时候，也是往左找，所以不受后面的i的影响，查询的时候只要保证查询区间长度不大与 $L$ 就行了。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int T;
int n,L;
struct node{
    ll a;
    int id;
    bool operator<(const node& h)const{return a<h.a||(a==h.a&&id>h.id);}
}h[maxn];
struct SegmentTree{
    int l,r;
    ll dat;
}tr[maxn<<2];
ll f[maxn];
void init(){
    memset(f,-1,sizeof(f));
}
void build(int rt,int l,int r){
    tr[rt].l=l,tr[rt].r=r;
    if(l==r){
        tr[rt].dat=-INF;
        return;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    tr[rt].dat=max(tr[rt<<1].dat,tr[rt<<1|1].dat);
}
void change(int rt,int x,ll v){
    if(tr[rt].l==tr[rt].r){
        tr[rt].dat=v;
        return;
    }
    int mid=tr[rt].l+tr[rt].r>>1;
    if(mid>=x) change(rt<<1,x,v);
    if(mid<x) change(rt<<1|1,x,v);
    tr[rt].dat=max(tr[rt<<1].dat,tr[rt<<1|1].dat);
}
ll query(int rt,int l,int r){
    if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].dat;
    int mid=tr[rt].l+tr[rt].r>>1;
    ll res=-INF;
    if(mid>=l) res=max(res,query(rt<<1,l,r));
    if(mid<r) res=max(res,query(rt<<1|1,l,r));
    return res;
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("HDU4719.in","r",stdin);
    scanf("%d",&T);
    for(int kase=1;kase<=T;kase++){
        init();
        printf("Case #%d: ",kase);
        scanf("%d%d",&n,&L);
        for(int i=1;i<=n;i++){
            scanf("%lld",&h[i].a);
            h[i].id=i;
        }
        sort(h+1,h+n+1);
        build(1,0,n);
        change(1,0,0);
        for(int i=1;i<=n;i++){
            ll res=query(1,max(0,h[i].id-L),h[i].id-1);
            if(res<0) continue;
            f[h[i].id]=res+h[i].a*h[i].a;
            change(1,h[i].id,f[h[i].id]-h[i].a);
        }
        if(~f[n]) printf("%lld\n",f[n]);
        else printf("No solution\n");
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

DP训练——线段树优化DP

线段树优化DP

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

动态规划