首页 > 其他分享 >[At_dp_w] Intervals & [At_dp_x] Tower

[At_dp_w] Intervals & [At_dp_x] Tower

时间:2024-11-08 20:41:11浏览次数:3  
标签:lazy le int max long Intervals Tower id dp

两道题都很好

Intervals

给定 \(m\) 条规则形如 \((l_i,r_i,a_i)\)​,对于一个 01 串,其分数的定义是:对于第 \(i\) 条规则,若该串在 \([l_i,r_i]\) 中至少有一个 1,则该串的分数增加 \(a_i\)

你需要求出长度为 \(n\) 的 01 串中的最大分数

\(1\le n,m\le 2\times 10^5,|a_i|\le 10^9\)


设计 \(f_{i,j}\) 表示考虑到第 \(i\) 个数,上一个 \(1\) 的位置在 \(j\) 得到情况

这里考虑一个经典 trick,为了避免区间重复贡献,钦定每个区间在右端点处取得贡献(由于区间在范围内选取,这必定不会影响最终的贡献值)

因此,考虑一个 \(f_{i,j}(i\neq j)\),当其从 \(f_{i-1,j}\) 转移过来的时候,由于 \(1\) 的状态不变,增加的只是右端点为 \(i\) 的贡献,此外还要要求在该区间内含有 \(1\),最优化地想,也就是最近的一个 \(1\) 包含在区间内,转移方程为 \(f_{i,j}=f_{i-1,j}+\sum\limits_{r_k=i\operatorname{and}l_k\le j}a_k\)

考虑 \(f_{i,i}\),由于我们在 \(i\) 新放了一个 \(1\),因此这个状态可以由任意一个 \(j\lt i\) 的 \(f_{i-1,j}\) 转移得到,额外的区间贡献计算方式不变,转移方程为 \(f_{i,j}=(\max\limits_{j}f_{i-1,j})+\sum\limits_{r_k=i\operatorname{and}l_k\le j}a_k\)

滚动数组优化的暴力
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int f[2][1000001];
struct gz{
    int l,r,a;
}a[1000001];
int ans=-0x7fffffffffffffff;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>a[i].l>>a[i].r>>a[i].a;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=i-1;++j){
            f[i&1][j]=f[(i-1)&1][j];
            for(int k=1;k<=m;++k){
                if(a[k].r==i and a[k].l<=j){
                    f[i&1][j]+=a[k].a;
                }
            }
        }
        for(int j=1;j<=i-1;++j){
            f[i&1][i]=max(f[i&1][i],f[(i-1)&1][j]);
        }
        for(int j=1;j<=m;++j){
            if(a[j].r==i and a[j].l<=i){
                f[i&1][i]+=a[j].a;
            }
        }
    }
    for(int i=0;i<=n;++i){
        ans=max(ans,f[n&1][i]);
    }
    cout<<ans;
}

事实上也可以优化到一维,优化之后少了从 \(f_{i-1,j}\) 到 \(f_{i,j}\) 的转移,更简洁了

优化到一维的暴力
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int f[1000001];
struct gz{
    int l,r,a;
}a[1000001];
int ans=0;
signed main(){
    cin>>n>>m;
    if(n>=5000) return 0;
    for(int i=1;i<=m;++i){
        cin>>a[i].l>>a[i].r>>a[i].a;
    }
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=i-1;++j){
            int t=f[j];
            for(int k=1;k<=m;++k){
                if(j<a[k].l and a[k].l<=i and a[k].r>=i){
                    t+=a[k].a;
                }
            }
            f[i]=max(f[i],t);
        }
        ans=max(ans,f[i]);
    }
    cout<<ans;
}

考虑我们的转移式 \(\sum\limits_{r_k=i\operatorname{and}l_k\le j}a_k\),可以发现这个转移式修改的位置是连续的,满足 \(j\in[l_k,i]\) 的 \(j\) 位置均可被这个 \(k\) 修改更新

由于我们压成一维之后已经把从 \(f_{i-1,j}\) 到 \(f_{i,j}\) 的转移省了,因此我们只需要考虑求那个形如 \(\max\) 的式子

区间修改,区间查最值,可以将 DP 数组放在线段树上处理

值得注意的是这个区间查最值的时候,由于 \(i\) 后面的值尚未更新,实际上约等于全局查最值,所以你其实根本没必要写一个查最值的函数

注意为了避免负贡献成最优解,查询的时候要对 \(0\) 取 \(\max\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,ans;
struct qj{
    int l,r,a;
};
vector<qj>a[400001];
namespace stree{
    struct tree{
        int maxn;
        int lazy;
    }t[400001*4];
    #define tol (id*2)
    #define tor (id*2+1)
    void pushdown(int id){
        if(t[id].lazy){
            t[tol].maxn+=t[id].lazy;
            t[tol].lazy+=t[id].lazy;
            t[tor].maxn+=t[id].lazy;
            t[tor].lazy+=t[id].lazy;
            t[id].lazy=0;
        }
    }
    void change(int id,int l,int r,int L,int R,int val){
        if(L<=l and r<=R){
            t[id].maxn+=val;
            t[id].lazy+=val;
            return;
        }
        int mid=(l+r)/2;
        pushdown(id);
        if(R<=mid) change(tol,l,mid,L,R,val);
        else if(L>=mid+1) change(tor,mid+1,r,L,R,val);
        else{
            change(tol,l,mid,L,mid,val);
            change(tor,mid+1,r,mid+1,R,val);
        }
        t[id].maxn=max(t[tol].maxn,t[tor].maxn);
    }
    int ask(){
        return max(0ll,t[1].maxn);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
	for(int i=1;i<=m;i++){
        int il,ir,ia;
        cin>>il>>ir>>ia;
        a[ir].push_back({il,ir,ia});
    }
    for(int i=1;i<=n;++i){
        stree::change(1,1,n,i,i,stree::ask());
        for(qj j:a[i]){
            stree::change(1,1,n,j.l,i,j.a);
        }
    }
    cout<<stree::ask();
}

Tower

直接买一赠一了吧

每个物品有 \(w,s,v\),表示重量,最大承重,价值,把物品堆在一起,要求每个物品上面堆着物品的总重量不超过这个物品的最大承重,问最大价值

\(n\le 10^3,w_i,s_i\le 10^4\)

这个题显然比上一个题水

首先看出这似乎是个背包,但是正常做背包显然做不出来(有后效性,先遍历过的物品有可能后选比较优),如果能找到某些性质使得先遍历的物品一定比后遍历的物品先选更优,那么这道题就能转化成背包问题

考虑两个物品 \(i,j\),设 \(i\) 放在 \(j\) 上面,那么 \(j\) 上面还能放的物品总质量为 \(s_j-w_i\),同理,如果 \(j\) 在上面,这个值为 \(s_i-w_j\)

由于 \(i,j\) 如何放,总重量都是一样的,对下面没有影响,因此 \(i\) 放在 \(j\) 上面更优,当且仅当 \(s_j-w_i\gt s_i-w_j\)

移项,\(s_i+w_i\lt s_j+w_j\),以此为比较依据直接背包即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct tower{
    int w,s,v;
    bool operator <(const tower&a)const{
        return w+s<a.w+a.s;
    }
}a[10001];
int f[20001];
int ans=0;
signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i].w>>a[i].s>>a[i].v;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i){
        for(int j=a[i].s;j>=0;--j){
            f[j+a[i].w]=max(f[j+a[i].w],f[j]+a[i].v);
        }
    }
    cout<<ans;
}

标签:lazy,le,int,max,long,Intervals,Tower,id,dp
From: https://www.cnblogs.com/HaneDaCafe/p/18535908

相关文章

  • Leetcode 474 dp数组讲解和滚动数组优化
    474.一和零​ ​dp[i][w1][w2]:DP数组的集合:考虑前i个物品包括第i个,满足背包重量不超过[w1][w2]的所有集合把输入数组中的每个string当作是一个物品,其重量分别为string中0和1的个数属性:价值每个物品的价值是1因为我们求最大子集的个数,一个字符串对子集个数贡献的......
  • 插入类DP
    对于这类题目的特征:1.排列性质2.\(100\len\le5\times10^3\)3.答案和排列的上升下降的突变点有关套路:按照某个从小到大的顺序插入,有了这个顺序就能算贡献或者方案数贡献往往提前计算,存在每个元素有新开一段、合并两端、连在某一段后面的不同方案有的允许了\(A\),\(W\),\(......
  • 大模型--训练 加速之 数据并行(DP, DDP与ZeRO)-上-12
    目录1.参考2.总结3.分布式数据并行(DDP)4.总结1.参考https://zhuanlan.zhihu.com/p/6171339712.总结以GoogleGPipe为代表的流水线并行范式,当模型太大,一块GPU放不下时,流水线并行,将模型的不同层放到不同的GPU上,通过切割mini-batch实现对训练数据的流水线处理,提升GPU计算......
  • 知识分享:Air780E软件之UDP应用示例
    一、UDP概述UDP(用户数据报协议,UserDatagramProtocol)是一种无连接的、不可靠的传输层协议,主要用于实现网络中的快速通讯。以下是UDP通讯的主要特点:1.1无连接通讯:UDP在发送数据之前不需要建立连接,这大大减少了通讯的延迟。发送方只需将数据包封装成UDP报文,并附上目的地址......
  • 洛谷 P2113 看球泡妹子(DP)
    传送门https://www.luogu.com.cn/problem/P2113解题思路可以设  表示前  场比赛看了  场,小红的满足度为  的最大精彩度。然后可以枚举前面的一个比赛 ,可以得到转移方程:但是,我们发现数组空间有一点小大,可以优化一下。发现每一次转移都是 ,于是可以滚动数组优化空......
  • P10161 [DTCPC 2024] 小方的疑惑 10 [构造 + 背包DP]
    P10161[DTCPC2024]小方的疑惑10Solution一开始看这题的时候,我们可能会觉得无从下手,这时不妨列出几种方案,计算它们的贡献,尝试得到一些启发。画来画去,发现无非就是并列和包含两种情况,并列就是()()()(),设它一共由\(x\)对括号组成,那么它的总贡献是\(x\times(x+1)\div......
  • 面试:TCP、UDP如何解决丢包问题
    文章目录一、TCP丢包原因、解决办法1.1TCP为什么会丢包1.2TCP传输协议如何解决丢包问题1.3其他丢包情况(拓展)1.4补充1.4.1TCP端口号1.4.2多个TCP请求的逻辑1.4.3处理大量TCP连接请求的方法1.4.4总结二、UDP丢包2.1UDP协议2.1.1UDP简介2.1.2......
  • 一类树形 dp
    省流:设计dp状态及转移,利用转移在链上复杂度低的特点或单独设计在链上的转移方式(并且这类dp合并的复杂度一般与子树大小有关),使得最劣情况相当于一棵满二叉树,得到较为优秀的复杂度。例题1给定一棵树,在树上选出一些点,使所有从根到叶子结点的路径上选出的点的个数相同。求方案......
  • CF的背包DP (备用笔记)
    源自vjudge上找到题目,都是背包DP的变式------(推荐点点前两个字......
  • intl 多语言国际化,自动补全locale,createNavigation ,createLocalizedPathnamesNaviga
     import{createNavigation}from'next-intl/navigation'exportconst{Link,redirect,usePathname,useRouter,getPathname}=createNavigation({locales,localePrefix,pathnames});页面的路由跳转和link 用这里导出的即可。 importcreateMiddlewaref......