left_right_2022

分类

题解(45)

/ 注册

全部文章（共3篇）

Codeforces 597C.Subsequences

题目描述：给定由1-n组成的长度为n的a[]和k，问长度为k+1的子序列中有多少个单调递增的？n<=1e5,k<=10 终于想到了！开k+1个线段树/树状数组记f[i][j][o]为前i个数，以j结尾，长度为o的子序列有多少个。i维可以省略，f[j][o]=f[Σ1-(j-1)][o-1...

树状数组线段树动态规划

2021-06-06

0 628

Codeforces 597B.Restaurant

题目描述：一家餐厅收到了n份订单，每份订单有开始和结束时间，餐厅可以选择接或不接，接受的订单时间必须互不重合，即任意一刻都不能被两个订单占用。问餐厅最多能接受几份订单。啊这，乍看是经典DP，但是不能直接写，需要多思考。以订单结束顺序排序。f[i]表示处理订单数为i时，所用的最小时间，发现f[i]有...

二分离散化动态规划

2021-06-06

0 527

Codeforces 1519D.Maximum Sum of Products

题意：你可以反转a数组的至多一段区间，求最大的Σaibi 先求一个不反转的前缀和,ans=sum[n]，枚举反转区间的中心和反转区间的长度，统计反转部分的和.ans=max(ans,反转部分的和-该区间原和+sum[n]);复杂度O(n^2) ```#include<bits stdc++.h...

前缀和动态规划区间

2021-04-30

0 662