区间\(DP\),入门题.环状\(DP\)先考虑线段.
我们用一个区间
\([l,r]\)表示石子,意义为该石子是由
\([l,r]\)区间的石子合并而来.
显然,最终一定只剩一堆石子
\([l,r]\),且
\(\exists k\)使得
\([l,r]\)先合并为
\([l,k]\)和
\([k+1,r]\)再合并为
\([l,r]\).
于是我们可以很自然的想到从左右端点重合的区间(即单个元素)开始向上递推.
由于最大值最小值情况相同,所以只讨论最大值.
于是,设
\(f_{i,j}\)表示把区间
\([l,r]\)合并起来能得到的最大值.
于是我们枚举断点就行了,不断递推即可.我们发现,转移需要快速求区间和.
所以还需要一个前缀和,记前缀和为
\(s_i\).
于是得到转移方程:
\[f_{i,j}=max(f_{i,j},f_{i,k}+f_{k+1,j}+s_j-s_{i-1})\]\(f\)数组的初值显然为
\(0\).
线段考虑完成之后,考虑环状怎么做.
显然,原数组倍长断环成链即可.
\(Code:\) #include #include #include #include #include #include #include #include #include #include #include
也是看起来非常不可做的一个题.
仔细思考,发现了一个很\(coooooooooool\)的事情:
他是不是让我求最小独立集覆盖...
一个独立集覆盖是指把图划分成若干个子集,每个子集里的点两两互不连通.
然后你\(2^n\)枚举子集,记录是不是一个独立集,然后在独立集上\(DP\).
你就令\(f_S\)表示点集为\(S\)时的最小独立集覆盖.
显然,每次可以从它一个是独立集的子集转移过来,取一个\(min\)就完了(最长路最短).
最后的答案是\(f_{U}-1\),其中\(U\)是全集.为什么减一啊?
因为最长路是边数啊...
#include #include #include #include #include #include #include #include #include #include #include
这个题并非只是简单的
\(\Theta(n^2)\)的
\(LCS\).
我们发现直接
\(\Theta(n^2)\)的
\(LCS\)显然过不去高达
\(10^5\)的数据.
但这题给了个奇妙的性质,它给的是两个排列.
也就是说,两个排列中的数字是相同的,唯一不同的就是数字的位置.
如果我们把第一个排列作为规定的大小顺序,那么我们发现,答案就是第二个排列在这个大小顺序下的
\(LIS\).
为什么呢?因为如果在第二个串中一个子序列是上升的,那么它在原序列中也一定是这样排列的.因为我们是按照第一个排列的顺序规定的大小.
所以就只需要映射完跑一遍
\(\Theta(n\times log_2n)\)的
\(LIS\)即可.
正好说一下
\(\Theta(n\times log_2n)\)的
\(LIS\)叭.
先来
\(\Theta(n^2)\)叭.
令
\(f_i\)表示以
\(i\)结尾的最长上升子序列的长度.
转移显然.
\[f_i=max_{j\in [1,i]\&\&v_j<v_i}{f_j}+1\] 我们发现这个状态是很难进行推广的.
于是考虑去改变状态.
令
\(f_i\)表示长度为
\(i\)的最长上升子序列的结尾元素目前可能的最小值.
因为我们当前最长上升子序列的结尾元素肯定是越小越好,这样我们才有更多的"空间"去放别的数字.
考虑这样如何转移:
令当前长度是
\(cnt\).
如果有
\(f_{cnt}<v_i\),则直接放入当前最长上升子序列的末尾,
\(++cnt\).
否则,考虑调整,由于
\(v_i\le f_{cnt}\),所以在长度较小的上升子序列中可能存在一个位置可供
\(v_i\)使用.
即把某个子序列中不如
\(v_i\)的结尾元素替换为
\(v_i\).
二分实现即可,显然
\(f\)数组具有单调性.
#include #include #include #include #include #include #include #include #include #include #include
水题.不知道为什么要写一遍,可能是太闲了叭(闲可不是好现象).
我直接上方程了:
令
\(f_i\)表示
\(1\)到
\(i\)中的最大子段和是多少.
\[f_i=max(f_{i-1}+v[i],v[i])\]完了.
其实这个还可以扩展至区间查询.很不巧,我会.是用线段树去维护.
虽然这不具有直接的区间可合并性,但我们可以考虑最大子段和在合并的时候的构成.
显然,构成有以下几种:
左区间的前缀,左区间的后缀+右区间的前缀,右区间的后缀,整个左区间+右区间的前缀,整个右区间+左区间的后缀,整个区间,左区间中部,右区间中部.
对,只需要
\(pushup\)的时候考虑这几种情况就行了.不过目前我还完全不会修改..只会静态的.
至于这个的例题,有:
原题代码
\(Code:\) #include #include #include #include #include #include #include #include #include #include #include
加强版代码:
\(Code:\) #include #include #include #define ls ( rt << 1 )#define rs ( rt << 1 | 1 )#define mid ( ( l + r ) >> 1 )#define int long longconst int N = 1e5 + 5 ;template < class T > inline T max ( T __A , T __B ) { return __A > __B ? __A : __B ; }struct seg { int left , right , data ; int ldata , rdata , mdata ;} t[(N<<2)] ;int n , m , v[N] ;inline void pushup (int rt) { t[rt].data = t[ls].data + t[rs].data ; t[rt].ldata = max ( t[ls].ldata , t[ls].data + t[rs].ldata ) ; t[rt].rdata = max ( t[rs].rdata , t[rs].data + t[ls].rdata ) ; t[rt].mdata = max ( t[ls].ldata , max ( t[rs].rdata , t[ls].rdata + t[rs].ldata ) ) ; t[rt].mdata = max ( t[rt].mdata , max ( t[ls].mdata , t[rs].mdata ) ) ; return ;}inline void prim (int rt , int val) { t[rt].data = t[rt].ldata = t[rt].rdata = t[rt].mdata = val ; return ; }inline void build (int rt , int l , int r) { t[rt].left = l ; t[rt].right = r ; if ( l == r ) { prim ( rt , v[l] ) ; return ; } build ( ls , l , mid ) ; build ( rs , mid + 1 , r ) ; pushup ( rt ) ; return ;}inline seg query (int rt , int ll , int rr) { int l = t[rt].left , r = t[rt].right ; if ( ll <= l && r <= rr ) return t[rt] ; if ( rr <= mid ) return query ( ls , ll , rr ) ; else if ( ll > mid ) return query ( rs , ll , rr ) ; else { seg lans = query ( ls , ll , rr ) , rans = query ( rs , ll , rr ) ; seg ans ; ans.data = lans.data + rans.data ; ans.ldata = max ( lans.ldata , lans.data + rans.ldata ) ; ans.rdata = max ( rans.rdata , rans.data + lans.rdata ) ; ans.mdata = max ( lans.ldata , max ( rans.rdata , lans.rdata + rans.ldata ) ) ; ans.mdata = max ( ans.mdata , max ( lans.mdata , rans.mdata ) ) ; return ans ; }}signed main () { scanf ("%lld" , & n ) ; for (int i = 1 ; i <= n ; ++ i) scanf ("%lld" , & v[i] ) ; scanf ("%lld" , & m ) ; build ( 1 , 1 , n ) ; while ( m -- ) { register int u , v ; scanf ("%lld%lld" , & u , & v ) ; printf ("%lld\n" , query ( 1 , u , v ).mdata ) ; } return 0 ;}
咕咕咕~