题目链接

另一种优化dp的解法

T 1 T1 T1

非常显然有一个 O ( n 2 ) O(n^2) O(n2)的 d p dp dp,虽然它的复杂度高的吓人,但还是让我们小心翼翼的把它写出来

定义 f [ 0 / 1 ] [ i ] [ j ] f[0/1][i][j] f[0/1][i][j]表示前 i i i个操作后,第 i i i次何左手/右手交换,且另一只手上是第 j j j次操作时的数

该状态是否存在,这样就是傻瓜式转移

然后考虑,这样设计状态是否合理?也就是 f [ 0 ] f[0] f[0]和 f [ 1 ] f[1] f[1]只需要维护是否可行,是一个 01 01 01数组

我们只需要知道 1 1 1的位置即可,也就是另一只手正握着什么数字

T 2 T2 T2

那么,让 f [ 0 ] f[0] f[0]成为一个 s e t set set,储存当第 i i i次左手成为持有手,右手中可行的【数字和下标】

显然 s e t set set的元素是一个 p a i r pair pair

当 k [ i ] k[i] k[i]不满足当前限制时,显然无法作为持有手,我们清空 f [ 0 ] f[0] f[0]

否则转移大概是这个样子

Ⅰ.上次是右手持有手,这次是左手持有手

当上一次的 f [ 1 ] f[1] f[1]有元素时,说明上一次右手作为持有手拿着数字 k [ i − 1 ] k[i-1] k[i−1]

这次我们尝试让左手变为持有手拿到 k [ i ] k[i] k[i],于是我们姑且把 { k [ i − 1 ] , i − 1 } \{k[i-1],i-1\} {k[i−1],i−1}插入 f [ 0 ] f[0] f[0]

Ⅱ.上次左手是持有手,这次还是左手

我们什么也不需要干,因为右手握着的数字没变,这些值上次就在 f [ 0 ] f[0] f[0]中了

于是乎,我们满足了左手的限制,现在是时候来考虑右手的限制了!!!

也就是遍历 f [ 0 ] f[0] f[0]中不满足限制条件的右手数字,移出 s e t set set

而且我们只需要从头尾删除即可(有单调性)

现在知道为什么用 s e t set set了吧!!因为可以快速找最小和最大啊!

f [ 1 ] f[1] f[1]的转移同理,于是可以在 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))的时间内解决问题

优化的本质,其实是考虑到第 i i i次和第 i − 1 i-1 i−1次,如果他们都以左手/右手作为持有手

那么第 i i i次只会在第 i − 1 i-1 i−1次删去大部分不合法的值,而至多添加一个新值,状态是 O ( n ) O(n) O(n)级别的

code

T 3 T3 T3

T 2 T2 T2优秀的复杂度足以通过这题,然而我们不止步于此

我们换种思路,考虑从后往前

也就是定义 f l [ i ] fl[i] fl[i]表示是否可以在第 i i i次用右手交换,而第 i − 1 i-1 i−1次是使用左手,且后缀 [ i , n ] [i,n] [i,n]都能延续下去

定义 f r [ i ] fr[i] fr[i]表示是否可以在第 i i i次使用左手交换,而第 i − 1 i-1 i−1次是使用右手,且后缀 [ i , n ] [i,n] [i,n]都能延续下去

这个状态设计是如此的巧妙,因为它只保存了在哪些位置中转,而且左右手中的数都是已知

我们说 f l [ i ] fl[i] fl[i]成立,必然是从某个 f r [ j ] fr[j] fr[j]转移而来(其中 j > i j>i j>i),此时满足

Ⅰ.对左手而言, i − 1 i-1 i−1次左手拿到的数字需要满足 [ i − 1 , j − 1 ] [i-1,j-1] [i−1,j−1]的所有限制

Ⅱ.对右手而言, [ i , j − 1 ] [i,j-1] [i,j−1]的卡片数字必须满足对应的右手限制,因为期间右手一直在换牌

暴力转移自然是 O ( n 2 ) O(n^2) O(n2)

然而我们发现,这个转移具有决策单调性,也就是越小的 j j j一定更优

于是我们只需要保存最小的 l a s 0 las0 las0使得 f l [ l a s 0 ] fl[las0] fl[las0]成立,保存最小的 l a s 1 las1 las1使得 f r [ l a s 1 ] fr[las1] fr[las1]成立

然后一边 d p dp dp的同时一边维护区间最值

实现起来很有技巧,细节很多,转移巧妙,达到严格 O ( n ) O(n) O(n)的复杂度

#include <bits/stdc++.h>using namespace std;const int maxn = 3e5+11; int n,m,a[maxn][2],b[maxn][2];int L[2],R[2],ok[2],k[maxn],pre[maxn][2];/*las0第i次用左手交换,而第i-1次是使用右手 las1相反。 */int main(){scanf("%d %d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d%d%d%d",&k[i],&a[i][0],&b[i][0],&a[i][1],&b[i][1]);int las0 = n+1, las1 = n+1;L[0] = L[1] = 0, R[0] = R[1] = m; ok[0] = ok[1] = 1;for(int i=n;i>=1;i--){ok[0] &= ( k[i]>=a[i][0] && k[i]<=b[i][0] );//左手一直换是否能到las1 ok[1] &= ( k[i]>=a[i][1] && k[i]<=b[i][1] );//右手一直换是否能到las0 L[0] = max( L[0],a[i][0] ), R[0] = min( R[0],b[i][0] );//保存左手限制的后缀最值 L[1] = max( L[1],a[i][1] ), R[1] = min( R[1],b[i][1] );//保存右手限制的后缀最值 int limit0 = ok[0] && k[i-1]>=L[1] && k[i-1]<=R[1];//i-1右手,i左手是否可行 int limit1 = ok[1] && k[i-1]>=L[0] && k[i-1]<=R[0];//i-1左手,i右手是否可行 if( limit0 )pre[i][0] = las1;//i-1是右手,i位置是左手由las1转移 if( limit1 )pre[i][1] = las0; if( limit0 )las0 = i, ok[1] = 1, L[0] = 0, R[0] = m;//因为i-1是右手,所以前面一段都是右手换,保存左手的极值 if( limit1 )las1 = i, ok[0] = 1, L[1] = 0, R[1] = m;}if( las0>1 && las1>1 )puts("No");else{puts("Yes");int id = las0>1;for(int i=1;i<=n;i=pre[i][id],id^=1 )for(int j=i;j<pre[i][id];j++)printf("%d ",id );}}