解题思路： 题目规定不能连续相邻两个房间偷，令dpi,0/1dp_{i,0/1}dpi,0/1​来表示节点iii为根可以偷到的最大价值，最终结果即max⁡(dp1,0,dp1,1)\max(dp_{1,0},dp_{1,1})max(dp1,0​,dp1,1​)。 假设iii被偷，则有：dpi,1+=dpi′s son,0dp_{i,1} += dp_{i's\ son,0}dpi,1​+=dpi′s son,0​ 假设iii没被偷， 则有dpi,0+=max⁡(dpi′s son,0,dpi′s son,1)dp_{i,0} += \max(dp_{...

解题思路 二叉树遍历通常利用递归的思想，粗略地写了一版(链接前向星存图），令ansansans表示二叉树中的最大路径和，ansians_iansi​表示以nodeinode_inodei​为节点的最大路径和，那么ansansans必定是ansians_iansi​中的某一个。 在遍历的过程中，对于任意一个节点iii的left分支和right分支,记录其较大者mxmxmx和较小者mnmnmn(注意不一定存在）,ans=max⁡(ans,wi,mx,wi+mx,wi+mn+mx)ans = \max(ans, w_i,mx,w_i+mx,w_i+mn + mx)ans=max(ans,wi​,m...

解题思路： 所有节点构成一个树，是无回路的无向图，但在这题中只要记录从根节点到叶节点方向的路径，使用链接前向星建立图。对于任一结点 nodei,i∈[1,n]node_i, i \in [1,n]nodei​,i∈[1,n],计算以该节点为root的子树中红色节点的个数，只要递归计算出其子树的红色节点个数以及其自己是否为红色即可。 令dpidp_idpi​为以iii为root的子树所包含的红色节点数，可以得出dpi=dpj+colori is ′Red′,j∈rooti′s sondp_i = dp_j + color_i\ is \ 'Red', j \in ...

解题思路： 这题应该是前面DP49的简化版，不需要高精度，令dpl,rdp_{l,r}dpl,r​表示左侧取lll个，右侧取rrr个的最大值，那么可以得到状态转移方程：dpl,r=max⁡(dpl−1,r+al×bi,dpl,r−1+an−r+1×bi)dp_{l,r} = \max(dp_{l-1,r} + a_l \times b_i, dp_{l,r-1} + a_{n-r+1} \times b_i)dpl,r​=max(dpl−1,r​+al​×bi​,dpl,r−1​+an−r+1​×bi​)。 #include<bits/stdc++.h> using names...

解题思路： 根据题目的提示，对于区间[l,r][l,r][l,r]，令dpl,rdp_{l,r}dpl,r​表示区间中需要的最少涂色次数，若colorl=colorrcolor_l = color_rcolorl​=colorr​，则dpl,rdp_{l,r}dpl,r​可以由dpl+1,rdp_{l+1, r}dpl+1,r​或者dpl,r−1dp_{l,r-1}dpl,r−1​转移过来，不会增加涂色次数，因为r或l可以由l或r直接一笔涂色完成。即最少涂色次数可以是:dpl,r=min⁡(dpl+1,r,dpl,r−1), colorl=colorrdp_{l,r} = \min...

解题思路： 问题分析为对于一个中序输入的树，根据规则找出组合积分最大值，即是以输入viv_ivi​做为rootrootroot，枚举每一个rootrootroot构成的树形所得到的最大积分。 对于每一个构成这棵树的子树也同样符合规则，从节点数2→n2 \to n2→n进行枚举每一个组合选出最大组合积分。令dpl,rdp_{l,r}dpl,r​表示从编号lll到编号rrr的最大积分值，则很容易得到状态转移方程：dpl,r=max⁡(dpl,r,dpl,root−1+dproot+1,r+vroot)dp_{l,r} = \max(dp_{l,r}, dp_{l,root-1} + dp_{ro...

解题思路： 因为题是一个项圈构成了环，所以使用两倍的长度存储能量项链v[2∗n]v[2*n]v[2∗n]。 令dpi,jdp_{i,j}dpi,j​表示从下标iii 到 下标jjj这一段合并所释放的能量。合并的长度由小到 大进行2→n2 \to n2→n。枚举每一段区间比较求得最大值。则有状态转移方程：dpi,j=dpi,k+dpk+1,j+vi∗vk+1∗vj+1dp_{i,j} = dp_{i,k}+dp_{k+1,j} + v_i * v_{k+1} * v_{j+1}dpi,j​=dpi,k​+dpk+1,j​+vi​∗vk+1​∗vj+1​。 没有看懂请手推一遍合并能量的计算公式。...

解题思路： 令dpi,jdp_{i,j}dpi,j​表示从下标i→ji \to ji→j的最小需要补充的符号数，即区间中不匹配的括号数。初始化 dpi,i=1dp_{i,i} = 1dpi,i​=1 则有状态转移方程dpi,j=dpi+1,j−1+match(i,j)，匹配为0，不匹配为2dp_{i,j} = dp_{i+1,j-1} + match(i,j)，匹配为0，不匹配为2dpi,j​=dpi+1,j−1​+match(i,j)，匹配为0，不匹配为2。 枚举k, k=i→j−1k, \ k = i \to j-1k, k=i→j−1。dpi,j=min⁡(dpi,...

解题思路： 行之间是独立的，取数时可以单行考虑，令dpl,rdp_{l,r}dpl,r​表示当前行从左取的个数和从右取的个数所得到的得分值。则dpl,r from dpl−1,r or dpl,r−1dp_{l,r} \ from \ dp_{l-1,r} \ or \ dp_{l,r-1}dpl,r​ from dpl−1,r​ or dpl,r−1​取最大值即可。 dpl,r=max⁡(dpl,r,dpl−1,r+vl∗2i,dpl,r−1+vr∗2i)dp_{l,r} = \max(dp_{l,r}, dp...

解题思路： 典型的01背包，转换结果为V−dpVV-dp_VV−dpV​,求dpVdp_VdpV​的最大值即可。 dpj=max⁡(dpj,dpj−vi+vi)dp_j = \max(dp_j, dp_{j-v_i}+v_i)dpj​=max(dpj​,dpj−vi​​+vi​) #include<bits/stdc++.h> using namespace std; int main(){ int V, n; ios::sync_with_stdio(false); cin>>V>>n; vector<int&gt...

解题思路： 输入时记录数组和sumsumsum， 如果sum%2≠0sum \% 2 \neq 0sum%2​=0直接输出false 否则令dpj（01背包）,(0≤j≤sum/2)dp_j（01背包）,(0 \leq j \leq sum/2)dpj​（01背包）,(0≤j≤sum/2)，表示处理第iii个数时，容量为jjj的背包，问题变为使用i和上一轮的值是否能构成jjj。 状态转移方程： dpj=1,(j=vi or dpj−vi≠0)dp_j = 1,(j = v_i\ or\ dp_{j-v_i} \neq 0)dpj​=1,(j=vi​ or&n...

解题思路： 完全背包下加条件，令dpjdp_jdpj​ 表示第iii种钱下，容量为jjj的背包，考虑dpj=0 or dpj−arri=0dp_j = 0\ or\ dp_{j-arr_i} = 0dpj​=0 or dpj−arri​​=0情况下状态方程： dpj=min⁡(dpj−arri+1,dpj),(dpj≠0,dpj+arri≠0)dp_j = \min(dp_{j-arr_i}+1, dp_j),(dp_j \neq 0 ,dp_{j+arr_i} \neq 0)dpj​=min(dpj−arri​​+1,dpj​),(dpj​​=0...

解题思路： 完全背包的变种，令dpjdp_jdpj​表示取到第iii个数的容量为jjj的背包（完全平方数之和），那么dpjdp_jdpj​的最大值一定是jjj本身（j∗1j*1j∗1），那么从2≤i≤n2 \leq i \leq \sqrt{n}2≤i≤n​之间做完全背包，有状态转移方程： dpj=min⁡(dpj−i2+1,dpj)dp_j = \min(dp_{j-i^2}+1,dp_j)dpj​=min(dpj−i2​+1,dpj​) #include<bits/stdc++.h> using namespace std; int main(){ int n; ...

解题思路： 令dp1jdp_{1j}dp1j​表示在选取第iii个物品时，容量为jjj的背包，由于是完全背包，有状态方程： dp1j=max⁡(dp1j,dp1j−vi+wi)dp_{1j} = \max(dp_{1j}, dp_{1j-v_i}+w_i)dp1j​=max(dp1j​,dp1j−vi​​+wi​) 等同于01背包的状态方程，但是完全背包同一个物品可以放入无数次，可以理解成:dp1j−vidp_{1j-v_i}dp1j−vi​​是在当前物品iii放入kkk次的结果，距离当前状态dp1jdp_{1j}dp1j​只有放入一次的距离。所以在推导的时候使用的时当前物品前一次放入的状...