• 斜率优化DP day47

    昨天忘记发了

    哦 好像double 范围是1.xx*e308 比ll 大多了 非常牛

    今天就要开始集训了喵

    难过qwq 不过期待派队的讲题和训练赛呢！

    1089. 烽火传递

    很简单把

    昨天忘了说的就是

    要是我们不想把本身这个元素算进去就可以把pushback 放在更新后面 但是 更新前面总是popfront

    1. #include 
    2. using namespace std;
    3. const int N = 2e5+10;
    4. const int M = 1<<12;
    5. //const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. int f[N],w[N],ans=inf;
    14. signed main(){
    15.     fast
    16.     int n,m;cin>>n>>m;
    17.     for(int i=1;i<=n;i++)cin>>w[i];
    18.     deque<int>dq;//min
    19.     dq.push_back(0);
    20.     for(int i=1;i<=n;i++){
    21.         while(!dq.empty()&&i-dq.front()>m)dq.pop_front();
    22.         if(!dq.empty())f[i]=f[dq.front()]+w[i];
    23.         while(!dq.empty()&&f[dq.back()]>=f[i])dq.pop_back();
    24.         dq.push_back(i);
    25.     }
    26.     for(int i=n-m+1;i<=n;i++){
    27.         ans=min(ans,f[i]);
    28.     }
    29.     cout<
    30.     return ~~(0^_^0);
    31. }

    1090. 绿色通道

    我超 一个样例 一直输出4

    我还以为写挂了

    原来我们得到的是min（长度为m的滑动窗口）还要-1 才是 空题段的len

    思路就是一眼二分 并且和上题一模一样啊

    1. #include 
    2. using namespace std;
    3. const int N = 5e4+10;
    4. const int M = 1<<12;
    5. //const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. int n,m,w[N];
    14. bool check(int mid){
    15.     int f[N];
    16.     deque<int>dq;//min qian m
    17.     dq.push_back(0);
    18.     for(int i=1;i<=n;i++){
    19.         while(!dq.empty()&&i-dq.front()>mid)dq.pop_front();
    20.         if(!dq.empty())f[i]=f[dq.front()]+w[i];
    21.         while(!dq.empty()&&f[dq.back()]>=f[i])dq.pop_back();
    22.         dq.push_back(i);
    23.     }
    24.     int ans=inf;
    25.     for(int i=n-mid+1;i<=n;i++){
    26.         ans=min(ans,f[i]);
    27.     }
    28.     if(ans<=m)return true;
    29.     else return false;
    30. }
    31. signed main(){
    32.     fast
    33.     cin>>n>>m;
    34.     for(int i=1;i<=n;i++)cin>>w[i];
    35.     int l=0,r=n;
    36.     while(l
    37.         int mid=(l+r)/2;
    38.         if(check(mid))r=mid;
    39.         else l=mid+1;
    40.     }
    41.     cout<-1<
    42.     return ~~(0^_^0);
    43. }

    1091. 理想的正方形

    二维的 不能就通常的 单调队列来看了

    我们可以先一行一行的看 把每个值存在他的左边

    然后再一列一列的看 那么就可以求出合法矩阵的max 和 min 了

    代码看起来有点多 其实都是一样的 而且也没啥细节注意

    1. #include 
    2. using namespace std;
    3. const int N = 1e3+10;
    4. const int M = 1<<12;
    5. //const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. int w[N][N],a,b,n,mx[N][N],mn[N][N];
    14. vector<int>c,d;
    15. void get_max(int x){
    16.     deque<int>dq;//max
    17.     for(int i=b;i>=1;i--) {
    18.         while (!dq.empty() && w[x][dq.back()] <= w[x][i])dq.pop_back();
    19.         dq.push_back(i);
    20.         while (!dq.empty() && dq.front() - i >= n)dq.pop_front();
    21.         mx[x][i] = w[x][dq.front()];
    22.     }
    23. }
    24. void get_min(int x){
    25.     deque<int>dq;//min
    26.     for(int i=b;i>=1;i--) {
    27.         while (!dq.empty() && w[x][dq.back()] >= w[x][i])dq.pop_back();
    28.         dq.push_back(i);
    29.         while (!dq.empty() && dq.front() - i >= n)dq.pop_front();
    30.         mn[x][i] = w[x][dq.front()];
    31.     }
    32. }
    33. void get_max1(int A[]){
    34.     deque<int>dq;//max
    35.     for(int i=a;i>=1;i--){
    36.         while(!dq.empty()&&A[i]>=A[dq.back()])dq.pop_back();
    37.         dq.push_back(i);
    38.         while(!dq.empty()&&dq.front()-i>=n)dq.pop_front();
    39.         if(i<=a-n+1)c.push_back(A[dq.front()]);
    40.     }
    41. }
    42. void get_min1(int B[]){
    43.     deque<int>dq;//max
    44.     for(int i=a;i>=1;i--){
    45.         while(!dq.empty()&&B[i]<=B[dq.back()])dq.pop_back();
    46.         dq.push_back(i);
    47.         while(!dq.empty()&&dq.front()-i>=n)dq.pop_front();
    48.         if(i<=a-n+1)d.push_back(B[dq.front()]);
    49.     }
    50. }
    51. signed main(){
    52.     fast
    53.     cin>>a>>b>>n;
    54.     for(int i=1;i<=a;i++)
    55.         for(int j=1;j<=b;j++)
    56.             cin>>w[i][j];
    57.     for(int i=1;i<=a;i++){
    58.         get_max(i);
    59.         get_min(i);
    60.     }
    61.     int A[N],B[N];
    62.     for(int i=1;i<=b-n+1;i++){
    63.         for(int j=1;j<=a;j++)A[j]=mx[j][i];
    64.         for(int j=1;j<=a;j++)B[j]=mn[j][i];
    65.         get_max1(A);
    66.         get_min1(B);
    67.     }
    68.     int ans=inf;
    69.     for(int i=0;isize();i++){
    70.         ans=min(ans,c[i]-d[i]);
    71.     }
    72.     cout<
    73.     return ~~(0^_^0);
    74. }

    300. 任务安排1

    这个题就是个暴力枚举

    但是我们这边可以用个费用提前计算的思想 为后面的斜率优化做铺垫

    状态表示 f[i]表示前i个合法方案的min

    我们可以写出这样的状态计算 我们要开一个time数组表示当前min状态下的时刻

    f[i]=min{f[j]+(time[j]+s+sumt[i]-sumt[j])*(sumc[i]-sum[j])};

    这里我们可以把s提前计算出来 这是啥意思 

    意思就是在我们这个点可以把该点取min时的 后面的s都加上去

    那我们就可以忽略s带来的变化了 直接可以不用记录time[]

    f[i]=min{f[j]+sumt[i]*(sumc[i]-sum[j])+s*(sumc[n]-sumc[j])}

    注意这里是 sumcn-sumcj啊 我们该段的s还是要算进去的

    1. #include 
    2. using namespace std;
    3. const int N = 5e3+10;
    4. const int M = 1<<12;
    5. //const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. int f[N],sumc[N],sumt[N],n,s;
    14. signed main(){
    15.     fast
    16.     cin>>n>>s;
    17.     for(int i=1;i<=n;i++){
    18.         int t,c;cin>>t>>c;
    19.         sumt[i]=sumt[i-1]+t;
    20.         sumc[i]=sumc[i-1]+c;
    21.     }
    22.     memset(f,0x3f3f,sizeof f);
    23.     f[0]=0;
    24.     for(int i=1;i<=n;i++){
    25.         for(int j=0;j
    26.             f[i]=min(f[i],f[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j]));
    27.         }
    28.     }
    29.     cout<
    30.     return ~~(0^_^0);
    31. }

    301. 任务安排2

    我囸 括号没打对 调了半天

    我们要先把j当成变量 把他变成一个一元二次方程来看

    这个就很想我们之前写的单调队列的题

    不过这里无法把j和i分离开 就不能那么简单的思考了

    斜率优化且满足ti为正 那么我们的斜率肯定是一直上升的

    那么我们只要单调队列中的点小于了我们此时的斜率那么就永远用不到了 删去即可

    此外cj 也是单调上升的 一定是在单调队列的右边

    我们维护 当前点与倒数第二个点的斜率要是小于等于最后一条线的斜率 那么最后一个点肯定没有

    用 删掉即可 这样子 就不用遍历每一个单调队列里的斜率 我们维护的单调队列的队头就是我们要的

    答案

    此题是运用了cj 和 ti 都是为正并且上升的性质 当然我们可以直接 二分来做捏

    1. #include 
    2. using namespace std;
    3. const int N = 3e5+10;
    4. const int M = 1<<12;
    5. //const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. int f[N],t[N],c[N],n,s;
    14. signed main(){
    15.     fast
    16.     cin>>n>>s;
    17.     for(int i=1;i<=n;i++){
    18.         cin>>t[i]>>c[i];
    19.         t[i]+=t[i-1];
    20.         c[i]+=c[i-1];
    21.     }
    22.     int q[N];
    23.     int hh=0,tt=0;
    24.     for(int i=1;i<=n;i++){
    25.         while(tt>hh&&(f[q[hh+1]]-f[q[hh]])<=(t[i]+s)*(c[q[hh+1]]-c[q[hh]]))hh++;
    26.         if(tt>=hh)f[i]=f[q[hh]]+t[i]*c[i]-(t[i]+s)*c[q[hh]]+s*c[n];
    27.         while(tt>hh&&(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt-1]])>=(f[i]-f[q[tt-1]])*(c[q[tt]]-c[q[tt-1]]))tt--;
    28.         q[++tt]=i;
    29.     }
    30.     cout<
    31.     return ~~(0^_^0);
    32. }

    302. 任务安排3

    继续上一道题

    这道题是二分来做

    并且我们维护单调队列时不能删队头 因为t不是大于0的

    所以斜率也不具有单调性

    还有我们二分的时候注意要判断边界 我们这里 用到了mid+1 

    但是我们可以想一下 当mid=r时因为是下取整 l=r 那根本不会循环进来喵

    还有就是俩ll相乘会溢出 必须用double转化一下 说实话我也不知道为啥 留个坑

    一些小理解：

    我们维护队列时 应该依照的是题目的题意来维护一个队列 

    比如今天我们就看到了两种情况 cj>=0的情况下 那么我们的曲线就都是在右边

    让后要是ti单调增 ->slope单调增 cj单调增->左端点一直向后移

    我们就可以维护一个下凸壳 要是当前k已经大于队头k 那么我们就可以直接删去 再也咩用了

    要是当前点与前面点能构成一个斜率更小的 那我们就要维护一个更小的下凸壳了

    简而言之就是

    （1） 斜率单调增 新加的点的横坐标也单调增

    在查询时，可以将队头小于当前斜率的点全部删掉

    在插入时，将队尾不在凸包赏的点全部删掉

    （2） 斜率不在具有单调性，但是新加的点的横坐标单调增

    在查询时，只能二分找

    在插入时，将队尾不在凸包赏的点全部删掉

    后面见到的后面再补喵

    1. #include 
    2. using namespace std;
    3. const int N = 3e5+10;
    4. const int M = 1<<12;
    5. //const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. uint f[N],t[N],c[N],n,s,q[N];
    14. signed main(){
    15.     fast
    16.     cin>>n>>s;
    17.     for(int i=1;i<=n;i++){
    18.         cin>>t[i]>>c[i];
    19.         t[i]+=t[i-1];
    20.         c[i]+=c[i-1];
    21.     }
    22.     int hh=0,tt=0;
    23.     for(int i=1;i<=n;i++){
    24.         int l=hh,r=tt;
    25.         while(l
    26.             int mid=(l+r)/2;
    27.             if((f[q[mid+1]]-f[q[mid]])>=(t[i]+s)*(c[q[mid+1]]-c[q[mid]]))r=mid;
    28.             else l=mid+1;
    29.         }
    30.         int j=q[l];
    31.         if(tt>=hh)f[i]=f[j]+t[i]*c[i]-(t[i]+s)*c[j]+s*c[n];
    32.         while(tt>hh&&(double)(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt-1]])>=(double)(f[i]-f[q[tt-1]])*(c[q[tt]]-c[q[tt-1]]))tt--;
    33.         q[++tt]=i;
    34.     }
    35.     cout<
    36.     return ~~(0^_^0);
    37. }

    303. 运输小猫

    调了半天 发现是方程就写错了额额

    题意很复杂 咋办

    简化一下

    我们知道每个饲养员有去无回 并且一开始猫就在某个山上了 玩到ti才肯走

    我们预处理出饲养员去每个山的前缀和d[i]

    我们饲养员的出发时间c[i]+前缀和d[i]>=t[i] 小猫才会跟我们走

    我们把s[i]单独列出来 因为这个就相当于是一个变量 让我们安排的

    c[i]>=t[i]-d[i]=A[i] 我们不妨设个A[i]=t[i]-d[i] 

    这里就需要一点操作了 我们可以把A[i] sort

    那我们要是出发时间>=a[i] 的都可以带走喵

    哦！ 并且我们还有p个饲养员 这不是一下就变成了 上一道题的翻版吗？

    熟悉的状态表示 f[i][j]表示 i 个人 在a[j] 时刻出发的min 状态量是 100*1e5 所以我们必须线性来做

    我们列出状态转移方程：

    f[i][j]=min{f[i-1][k]-(s[j]-s[k])+(j-k)*a[j]} (手动模拟一下就可以了

    我们把有关k的变量 设为x y

    f[i-1][k]+s[k]  =  a[j] * k +f[i][j]-j*a[j]+s[j];

            y               斜率    x    min且>=0

    我们可以发现 斜率a单调增 k从0到j枚举单调 所以是昨天的第一种

    查询时要是当前斜率大于队头 删除队头

    插入时要是当前斜率小于队尾 删除队尾

    ok over 了 还有一定要注意状态转移方程写没写对啊 这里只有更新时才会用到状态转移方程 很难

    发现啊！

    小技巧：我们写的时候可以画个图 把横坐标 纵坐标 代表啥写出来 再把不等式列出来 到时候照抄

    就行了 不容易出错喵

    1. #include 
    2. using namespace std;
    3. const int N = 1e5+10;
    4. const int M = 1<<12;
    5. //const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. int n,m,p,f[110][N],a[N],d[N],q[N],s[N];
    14. int get_y(int k,int i){
    15.     return f[i-1][k]+s[k];
    16. }
    17. signed main(){
    18.     fast
    19.     cin>>n>>m>>p;
    20.     for(int i=2;i<=n;i++)cin>>d[i],d[i]+=d[i-1];
    21.     for(int i=1;i<=m;i++){
    22.         int h,t;cin>>h>>t;
    23.         a[i]=t-d[h];
    24.     }
    25.     sort(a+1,a+m+1);
    26.     for(int i=1;i<=m;i++){
    27.         s[i]=s[i-1]+a[i];
    28.     }
    29.     memset(f,0x3f3f,sizeof f);
    30.     for(int i=0;i<=p;i++)f[i][0]=0;
    31.     for(int i=1;i<=p;i++){
    32.         int hh=0,tt=0;
    33.         for(int j=1;j<=m;j++){
    34.             while(tt>hh&&a[j]*(q[hh+1]-q[hh])>=(get_y(q[hh+1],i)-get_y(q[hh],i)))hh++;
    35.             int k=q[hh];
    36.             if(tt>=hh)f[i][j]=f[i-1][k]+(j-k)*a[j]-(s[j]-s[k]);
    37.             while(tt>hh&&(double)(get_y(q[tt],i)-get_y(q[tt-1],i))*(j-q[tt-1])>=(double)(get_y(j,i)-get_y(q[tt-1],i))*(q[tt]-q[tt-1]))tt--;
    38.             q[++tt]=j;
    39.         }
    40.     }
    41.     cout<<
    42.     return ~~(0^_^0);
    43. }

     

  • 相关阅读:
    第46屆ICPC 東亞洲區域賽（澳門）
    DynamicProgramming 动态规划
    c++命名空间，缺省参数，引用
    为dev c++配置图形开发环境easyx
    如何使用 SwiftUI 支持夜色模式？
    设计模式 建造者模式介绍、案例应用、建造者模式和工厂模式的区别
    （黑马出品_02）SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式
    北邮22级信通院数电：Verilog-FPGA（9）第九周实验（1）实现带同步复位功能、采用上升沿触发的D触发器
    Linux 基础-文本处理命令
    商业精英的首选
  • 原文地址：https://blog.csdn.net/qq_23852555/article/details/126099519