网站的查询系统怎么做,个人做网站能备案吗,金华农村网站建设,网络热词缩写0x53 区间DP
到目前为止#xff0c;我们介绍的线性DP一般从初态开始#xff0c;沿着阶段的扩张向某个方向递推#xff0c;直至计算出目标状态。区间DP也属于线性DP中的一种#xff0c;它以“区间长度”作为DP的“阶段”#xff0c;使用两个坐标#xff08;区间的左右端点…0x53 区间DP
到目前为止我们介绍的线性DP一般从初态开始沿着阶段的扩张向某个方向递推直至计算出目标状态。区间DP也属于线性DP中的一种它以“区间长度”作为DP的“阶段”使用两个坐标区间的左右端点描述每个维度。在区间DP中一个状态由若干个比它更小且包含于它的区间所代表的状态转移而来因此区间DP的决策往往就是划分区间的方法。区间DP的初态一般就由长度为1的“元区间”构成。这种向下划分、再向上递推的模式与某些树形结构例如0x43节的线段树有很大的相似之处。我们把区间DP作为线性DP中一类重要的分支单独进行讲解使下一节树形DP的内容更容易理解。同时借助区间DP这种与树形相关的结构我们也将提及记忆化搜索——其本质是动态规划的递归实现方法。 “多边形”是一款单人益智游戏。在游戏开始时系统给定玩家一个 N N N边形该 N N N边形由 N N N个顶点和 N N N条边构成每条边连接两个相邻的顶点。在每个顶点上写有一个整数可正可负。在每条边上标有一个运算符“”加号或“*”乘号。 第一步玩家选择一条边将它删除。接下来在进行 N − 1 N-1 N−1步在每一步中玩家选择一条边把这条边以及该边连接的两个顶点用一个新的顶点代替新顶点上的整数值等于删去的两个顶点上的数按照删去的边上标有的符号进行计算得到的结果。如下图所示就是一盘游戏的过程。 最终游戏仅剩一个顶点顶点上的数值就是玩家的得分上图玩家得分为 0。 请计算对于给定的 N N N边形玩家最高能获得多少分以及第一步有哪些策略可以使玩家获得最高得分。 3 ≤ N ≤ 50 3\leq N \leq 50 3≤N≤50, 数据保证无论玩家如何操作顶点上的数值均在 [ − 32768 , 32767 ] [−32768,32767] [−32768,32767]之内。 在枚举第一步删除哪条边后这道题就与“石子合并”非常相似仍是在每一步中对两个相邻的元素做某种运算合成一个。简便起见我们把被删除的边逆时针方向的顶点称为“第一个顶点”依次类推。容易想到使用 F [ l , r ] F[l,r] F[l,r]表示把 l l l到 r r r个顶点合成一个顶点后顶点上的数值最大是多少。
然而在使用动态规划解决每一道问题时都时刻牢记动态规划的“三要素”和使用动态规划的“三前提”。把“顶点上的最大数值”作为每一个子问题 [ l , r ] [l,r] [l,r]的代表信息不符合动态规划的“最优子结构”性质。因为负数的存在进行乘法运算时大区间 [ l , r ] [l,r] [l,r]的顶点的最大数值不能由区间 [ l , k ] [l,k] [l,k]和区间 [ k 1 , r ] [k1,r] [k1,r]合成的两个顶点的最大数值导出——因为区间 [ l , k ] [l,k] [l,k]和区间 [ k 1 , r ] [k1,r] [k1,r]合成的两个顶点的最小数值可能是很小的负数负负相乘得正运算结果可能更大。
不过上面的反例也启发我们如果把一个区间 [ l , r ] [l,r] [l,r]能够合成的顶点上的最大和最小数值同时作为子问题 [ l , r ] [l,r] [l,r]的代表信息是否满足最优子结构性质答案是肯定的。最大值的来源只可能是两个最大值相加、相乘或是两个最小值相乘负负得正或一个最大值与一个最小值相乘当其中一个子区间的最大、最小值都是正数而另一个都是负数时。最小值的来源只可能是两个最小值相加、相乘或是两个最大值相乘或一个最大值与一个最小值相乘。
因此可以设 f [ l , r , 1 ] f[l,r,1] f[l,r,1]表示把第 l l l到 r r r个顶点合成一个顶点后顶点上的数值最大是多少设 f [ l , r , 0 ] f[l,r,0] f[l,r,0]表示把第 l l l到 r r r个顶点合成一个顶点后顶点上的数值最小是多少。枚举区间的划分点 k k k决策状态转移方程如下 f [ l ] [ r ] [ 1 ] max l ≤ k r { f [ l ] [ k ] [ 1 ] f [ k 1 ] [ r ] [ 1 ] f [ l ] [ k ] [ p ] ∗ f [ k 1 ] [ r ] [ q ] , p , q ∈ { 0 , 1 } f[l][r][1]\underset{l\leq k r}\max \left\{\begin{array}{l}f[l][k][1]f[k1][r][1] \\ f[l][k][p]*f[k1][r][q],p,q\in\{0,1\} \end{array}\right. f[l][r][1]l≤krmax{f[l][k][1]f[k1][r][1]f[l][k][p]∗f[k1][r][q],p,q∈{0,1} f [ l ] [ r ] [ 0 ] min l ≤ k r { f [ l ] [ k ] [ 0 ] f [ k 1 ] [ r ] [ 0 ] f [ l ] [ k ] [ p ] ∗ f [ k 1 ] [ r ] [ q ] , p , q ∈ { 0 , 1 } f[l][r][0]\underset{l\leq k r}\min \left\{\begin{array}{l}f[l][k][0]f[k1][r][0] \\ f[l][k][p]*f[k1][r][q],p,q\in\{0,1\} \end{array}\right. f[l][r][0]l≤krmin{f[l][k][0]f[k1][r][0]f[l][k][p]∗f[k1][r][q],p,q∈{0,1}
初值 ∀ l ∈ [ 1 , N ] , F [ l , l , 0 ] F [ l , l , 1 ] A l \forall l \in [1,N],F[l,l,0]F[l,l,1]A_l ∀l∈[1,N],F[l,l,0]F[l,l,1]Al其余均为正或负无穷。
目标 F [ 1 , N , 1 ] F[1,N,1] F[1,N,1]。
上述算法的时间复杂度为 O ( N 4 ) O(N^4) O(N4)。实际上我们还可以进一步优化掉枚举第一步删除哪条边耗费的时间。在游戏最初我们选择一条边删掉然后把剩下的“链”复制一倍接在末尾以被删除的边逆时针方向的第一个顶点为开头如下图所示 在这个边长为 2 N 2N 2N的“链”上 ∀ i ∈ [ 1 , N ] \forall i\in [1,N] ∀i∈[1,N]的区间 [ i , i N − 1 ] [i,iN-1] [i,iN−1]合并成一个顶点就等价于原游戏的第一步删掉第 i i i个顶点逆时针一侧的边然后把剩余的部分合并成一个顶点。因为区间长度是DP的阶段我们只需要对前 N N N个阶段进行DP每个阶段只有不超过 2 N 2N 2N个状态总时间复杂度降低为 O ( N 3 ) O(N^3) O(N3)。最后的答案是 max 1 ≤ i ≤ N { F [ i , i N − 1 ] } \underset{1\leq i\leq N} \max\{ F[i,iN-1] \} 1≤i≤Nmax{F[i,iN−1]}。
#include bits/stdc.h
using namespace std;int N;
int a[110];
char op[110];
int dp[110][110][2];int main()
{scanf(%d,N);for(int i1;iN;i){getchar();scanf(%c %d,op[i],a[i]);}for(int iN1;i2*N;i)op[i]op[i-N],a[i]a[i-N];for(int i1;i2*N;i)for(int j1;j2*N;j)dp[i][j][0]0x3f3f3f3f,dp[i][j][1]0xcfcfcfcf;for(int len1;lenN;len){for(int l1;llen-12*N;l){int rllen-1;if(len1){dp[l][r][0]dp[l][r][1]a[l];continue;}for(int kl;kr;k){if(op[k1]t){dp[l][r][0]min(dp[l][r][0],dp[l][k][0]dp[k1][r][0]);dp[l][r][1]max(dp[l][r][1],dp[l][k][1]dp[k1][r][1]);}else{for(int i0;i2;i)for(int j0;j2;j){dp[l][r][0]min(dp[l][r][0],dp[l][k][i]*dp[k1][r][j]);dp[l][r][1]max(dp[l][r][1],dp[l][k][i]*dp[k1][r][j]);}}}}}int ans0xcfcfcfcf;for(int i1;iN;i)ansmax(ans,dp[i][iN-1][1]);printf(%d\n,ans);for(int i1;iN;i)if(ansdp[i][iN-1][1])printf(%d ,i);return 0;
}这种“任意选择一个位置断开复制形成两倍长度的链”的方法是解决DP中环形结构的常用手段之一我们会在0x55节进一步探讨。 虽然探索金字塔是极其老套的剧情但是有一队探险家还是到了某金字塔脚下。 经过多年的研究科学家对这座金字塔的内部结构已经有所了解。 首先金字塔由若干房间组成房间之间连有通道。 如果把房间看作节点通道看作边的话整个金字塔呈现一个有根树结构节点的子树之间有序金字塔有唯一的一个入口通向树根。 并且每个房间的墙壁都涂有若干种颜色的一种。 探险队员打算进一步了解金字塔的结构为此他们使用了一种特殊设计的机器人。 这种机器人会从入口进入金字塔之后对金字塔进行深度优先遍历。 机器人每进入一个房间无论是第一次进入还是返回都会记录这个房间的颜色。 最后机器人会从入口退出金字塔。 显然机器人会访问每个房间至少一次并且穿越每条通道恰好两次两个方向各一次 然后机器人会得到一个颜色序列。 但是探险队员发现这个颜色序列并不能唯一确定金字塔的结构。 现在他们想请你帮助他们计算对于一个给定的颜色序列有多少种可能的结构会得到这个序列。 因为结果可能会非常大你只需要输出答案对 1 0 9 10^9 109取模之后的值。 输入仅一行包含一个字符串 S S S长度不超过 300表示机器人得到的颜色序列。 例如序列“ABABABA”对应5种金字塔结构最底层是树根。我们认为子树之间是有序的所以方案3和方案4是两种不同的方案。如下图所示。 在0x21节中我们提到过一棵树的每棵子树都对应着这棵树的DFS序中的一个区间。本题中记录的序列虽然不是DFS序但仍满足这条性质。因此这道题目在“树形结构”与“字符串”之间通过“子树”和“区间”建立了联系。结合本节前半部分对区间DP的分析不难想到用 F [ l , r ] F[l,r] F[l,r]表示子串 S [ l ∼ r ] S[l\sim r] S[l∼r]对应着多少种可能得金字塔结构树形结构。
接下来我们考虑对区间的划分。以上图中的方案3为例序列“ABABABA”被分成五个部分 同理方案5把序列分成“A|B|A|B|A|B|A”七个部分。也就是说若子串 S [ l ∼ r ] S[l\sim r] S[l∼r]对应一棵子树则 S [ l 1 ] , S [ r − 1 ] S[l1],S[r-1] S[l1],S[r−1]两个字符是进入和离开时产生的。除此之外 [ l , r ] [l,r] [l,r]包含的每棵更深的子树都对应着一个子问题会产生 [ l , r ] [l,r] [l,r]中的一段。相邻两段之间还有途径树根产生的一个字符。因此 [ l , r ] [l,r] [l,r]包含的子树个数可能不止两个如果我们像前面的题目一样采用朴素算法枚举子串 S [ l ∼ r ] S[l\sim r] S[l∼r]划分点的数量和所有划分点的位置那么时间复杂度会变得非常高。
把子串 S [ l ∼ r ] S[l\sim r] S[l∼r]分成两部分每部分可由若干棵子树组成。不过这样可能会产生重复计数。如果每段可以由多颗子树构成那么划分方案“A|BAB|A|B|A”和“A|B|A|BAB|A”中的”BAB“都能产生”B|A|B“两颗子树最终归为同一结果——方案5。
实际上为了解决让计数不重不漏我们可以只考虑子串 S [ l ∼ r ] S[l\sim r] S[l∼r]的第一棵子树是由哪一段构成的。枚举划分点 k k k令子串 S [ l 1 ∼ k − 1 ] S[l1\sim k-1] S[l1∼k−1]构成 [ l , r ] [l,r] [l,r]的第一棵子树 S [ k ∼ r ] S[k\sim r] S[k∼r]构成 [ l , r ] [l,r] [l,r]的剩余部分其他子树。如下图所示。 如果 k k k不相同那么子串 S [ l 1 ∼ k − 1 ] S[l1\sim k-1] S[l1∼k−1]代表的子树的大小也不相同就不可能产生重复计算的结构。于是我们可以得到状态转移方程 F [ l , r ] { 0 , S [ l ] ≠ S [ r ] ∑ l 2 ≤ k ≤ r , S [ l ] S [ k ] F [ l 1 , k − 1 ] ∗ F [ k , r ] , S [ l ] S [ r ] F[l,r]\left \{\begin{array}{l} 0,S[l]\neq S[r] \\ \underset{l2\leq k\leq r,S[l]S[k]}\sum F[l1,k-1]*F[k,r],S[l]S[r] \end{array} \right. F[l,r]{0,S[l]S[r]l2≤k≤r,S[l]S[k]∑F[l1,k−1]∗F[k,r],S[l]S[r] 初值 ∀ l ∈ [ 1 , N ] , F [ l , l ] 1 \forall l\in[1,N],F[l,l]1 ∀l∈[1,N],F[l,l]1其余均为0。目标 F [ 1 , N ] F[1,N] F[1,N]。
这道题告诉我们对于方案计数类的动态规划问题通常一个状态的各个决策之间满足“加法原理”而每个决策划分之间的几个子状态满足“乘法原理”。在设计状态转移方程的决策方案与划分方法时一个状态的所有决策之间必须具有互斥性才能保证不会出现重复问题。在0x5c节中我们会进一步探讨计数类DP的相关模型与求解策略。
#include bits/stdc.h
using namespace std;char s[305];
int dp[305][305];
const int p1e9;int main()
{scanf(%s,s1);int Nstrlen(s1);for(int len1;lenN;len){for(int l1;llen-1N;l){int rllen-1;if(len1){dp[l][r]1;continue;}if(s[l]s[r])for(int kl2;kr;k)if(s[l]s[k])dp[l][r](dp[l][r]dp[l1][k-1]*(long long)dp[k][r])%p;}}printf(%d,dp[1][N]);return 0;
}在具体的程序编写中区间DP不仅可以用递推若干循环来实现也可以用递归记忆化搜索来实现。把子问题的求解过程写成一个函数 s o l v e ( l , r ) solve(l,r) solve(l,r)枚举划分点 k k k递归求解 s o l v e ( l 1 , k − 1 ) solve(l1,k-1) solve(l1,k−1)和 s o l v e ( k , r ) solve(k,r) solve(k,r)回溯时把二者的结果相乘加到 s o l v e ( l , r ) solve(l,r) solve(l,r)的结果中。在上述过程中一个区间 [ l , r ] [l,r] [l,r]对应的函数 s o l v e ( l , r ) solve(l,r) solve(l,r)可能会被调用多次我们可以建立一个全局函数 F F F在第一次计算完 s o l v e ( l , r ) solve(l,r) solve(l,r)时把结果保存在 F [ l , r ] F[l,r] F[l,r]中之后 s o l v e ( l , r ) solve(l,r) solve(l,r)再被调用时就可以直接返回 F [ l , r ] F[l,r] F[l,r]。这样带有记忆化的搜索就保证了每个区间只会求解一次时间复杂度仍然是 O ( N 3 ) O(N^3) O(N3)。
int f[305][305],p1e9;
int solve(int l,int r)
{if(lr) return 0;if(lr) return 1;if(f[l][r]!-1) return f[l][r]; //记忆化f[l][r]0;for(int kl2;kr;k)f[l][r](f[l][r](long long)solve(l1,k-1)*solve(k,r))%p;return f[l][r];
}memset(f,-1,sizeof(f));
solve(1,N);
