[DP][二分][经典][×] UVA 1443 Garlands

没做出来看题解的时候就在想出题人是怎么搞出来的。。。这个做法emm

最大值最小化肯定要想二分,但是二分后这题目怎么check是个技术活。我最悲催的是理解错了题目意思,以为这些珠子(不管是什么吧我感觉是珠子)可以互换位置。实际上是不可以换的emm所以说看题还是要好好搞明白。

然后说说这个check,这个一开始有点迷,因为它本身是dp那一章的题,但是二分的check一般都是判断一个可行性,那加了这个二分出来的答案的约束怎么判断可行性?首先可以确定一般dp不会说去dp那种“区间上的最大值”之类的东西,他要做一定是一个量化的东西去求最优解。这里的话可以想象一下,如果用了比m更少的段就可以满足要求那么就可以继续进行下去?这样的话必须保证段数和最紧的上限是一个正比的关系!但是算一算可以发现并没有这种正比关系,一般这时候就放弃用二分的方法了,但是这个题最精彩的地方就在于他的奇偶性,由于题目本身一直在要求“半段”,所以可以利用奇偶性来保证正比单调,具体可以看这位dalao的博客

继续阅读“[DP][二分][经典][×] UVA 1443 Garlands”

[线性结构DP][经典] UVA10271 Chopsticks

https://cn.vjudge.net/problem/UVA-10271

确实是经典。。。这种一开始没有什么头绪的dp,可以自己写出来几组样例,从中发掘最优解的性质,从而找到入手点。经过这样的一个xjb试探之后发现了:最优解的每组筷子中的短的那两根必定是在有序序列中相邻的。这样的话就可以确定一个转移的方法了,类似于背包里对于每个物品选还是不选,在这里对于每根筷子确定选还是不选,如果选,根据上面的性质他必须和之前的那根筷子组成一副。由此可以确定一个最基本的转移方程形式dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(len[i]-len[i-1])^2),dp[i][j]表示对于前i个筷子分给j个人的最优解。这里还有一个问题是必须要给每个人再分一根最长的筷子,其实可以发现这个条件更好处理,只要满足i>=3*j就可以了:因为这个最长的筷子其实只要比另外俩长就可以,所以在最优解中的这根筷子有些人之间甚至可以换着用,顺序也无所谓,满足这个条件一定能分配好的。

对于这个状态转移方程,可以确定一个边界条件是dp[i][0]=0(从转移方程的第二部分可以得出来)

继续阅读“[线性结构DP][经典] UVA10271 Chopsticks”

[坑][计算几何][极角排序][利用已有信息] UVALive 4064 Magnetic Train Tracks

https://cn.vjudge.net/problem/UVALive-4064

简单的极角排序应用,枚举每个点作为角点,然后按照角度顺时针枚举另一个点,在这个过程中递推记录下对于枚举的点有多少个钝角/直角出现。由于一个钝角/直角唯一的对应一个钝角/直角三角形,因此最后只需要把C(n,3)-钝角数量作为答案即可。

坑点:lrj的书上和各位dalao的blog都说的是锐角直角,呵呵,wa了两个多小时最后翻别人代码发现是只能锐角不能直角,服了,改了就过了,也不知道网上这么多人都写得锐角或者直角是怎么写出来只能锐角的代码的。

继续阅读“[坑][计算几何][极角排序][利用已有信息] UVALive 4064 Magnetic Train Tracks”

[紫书][DP][计算几何] UVA1634 The Picnic

题目链接 https://cn.vjudge.net/problem/UVA-1634

最近有把紫书dp这一章的习题搞完的打算。。。这个题本来看vjudge上就不到20个人做想放弃的,强迫症导致开了题就得ac。

其实和之前的那个极角排序的题目感觉很像,只不过如果还是按照那个思维来的话会遇到一个问题无法解决,就是不能在保证为凸多边形的情况下满足无后效性。。。这个光从样例就可以试出来,所以就卡了半小时没有头绪。索性直接搜了。。。但是没想到这个搜题解讲的也很迷而且做的人很少,就直接去vjudge看了代码,看到dp是二维的和转移方程顿时懂了,和之前那个题一样都是枚举左下角的点,但是这个要求dp的时候考虑两维,也就是dp[i][j]表示当前左下角点对应的以i为顺时针倒数第一个点(也就是紧挨着枚举点s的点)且以就j为顺时针倒数第二个点的最大多边形面积。 继续阅读“[紫书][DP][计算几何] UVA1634 The Picnic”

[数学][计算几何][极角排序][递推] UVA 11529 Strange Tax Calculation

题目链接 https://cn.vjudge.net/problem/UVA-11529

(复习期末期间日常的小题
想到了考虑每个点被多少个三角形包围,但是没想到怎么算。。。主要还是计算几何太萎le,完全没有想到可以极角排序处理emmm。

具体的就是,考虑每一个点被多少个三角形包含,但是直接考虑也不好计算,可以考虑反向计算出不被多少个三角形包含,这个计算就要用到极角排序了。。。循环遍历每个点,在每个xi点,都对所有的其他点(姑且称为角点吧)相对于这个xi点的极角做一个排序,然后利用三角形的性质,选一个方向(顺时针或者逆时针都行),依次考虑“以每个角点为最小极角与之角度差小于pi的最大角度点之间有多少个点“,可能难以理解,画个图就好了,算出来点的数量p(p包含最大的那个点)之后C(p,2)就是“包含当前最小角点的所有的不覆盖xi点的三角形数量”,依次累加就好了。。。

另外,画个图就会发现,还需要考虑圆周转一圈的情况,所以要把排序后的极角数组复制一遍,而且复制出来的这个数组每个元素还要加2pi!(这个自己试试就知道了)

然后就是找最大点的步骤要小心,很容易写错。。莫名其妙,也可能是我最近复习微机原理复习傻了。 继续阅读“[数学][计算几何][极角排序][递推] UVA 11529 Strange Tax Calculation”

[DP][紫书][计算几何] UVA 1543 Telescope

题目链接 https://cn.vjudge.net/problem/UVA-1543

复习微机原理复习到吐,随便翻了个题写了写缓和一下脑子。。。。

一开始看题目给的信息总想着怎么能用到那个1/2sinα,然后就没什么头绪(后来发现给这公式只是用来计算三角形的)。后来开始想正常的dp套路,也就是以xx为结尾/开头的xx的大小,然后发现这个形状的大小不能只由一边来确定,所以加了一维表示另外一边的位置,最后整出来状态就是dp[i][j][k]表示在i到j之间选k个点能组成的最大的多边形大小 继续阅读“[DP][紫书][计算几何] UVA 1543 Telescope”

[二维DP][组合计数][利用对称性简化问题] UVALive 3295

https://vjudge.net/problem/UVALive-3295

这个题目和3720很像,尤其是在应用对称性的时候。这种题目有个很有趣的地方就是他每次都是对局部进行刻画然后得到了全局的信息,或者可以这么说,按照某一种策略使得某种属性所有的状态都被考虑进去。在这里就是计算一个共线的点的问题,按照和题目3720算法本身的推其实是只能算出来“斜率为正”的一类斜线,但是算的是“所有的斜率为正”的斜线,也就是覆盖了每一种情况,那么剩下的情况其实只有水平竖直和斜率为负的斜线,但是由对称性可知斜率为负的斜线一定和斜率为正的斜线数量相等,因此只需要*2即可,而我自己一开始一直在纠结的问题就是怎么算出来这些反向斜线,其实最后全局考虑只需要把算出来的正向斜线情况*2即可。最后的结果就是C(3,(m+1)*(n+1))-共线的三点数量。
wa的话有一个问题是,在gcd的算法中如果a和b有一个数字为0那么返回值就会是0,这种情况在这里的递推过程中是会出现问题的,需要注意让循环从2开始,也算是一个小小的坑吧。。以前没有注意到。

继续阅读“[二维DP][组合计数][利用对称性简化问题] UVALive 3295”

[数位DP][组合数学][整数分段] UVa 11038 How Many O’s?

自己写了个有点繁杂的数位dp,本来一发过还有点高兴,但是看了前排dalao代码发现自己写的太复杂了。。。。这个题其实只用组合数学就可以解emmmm

先上自己的屌丝做法:分段dp,从前往后,组合数学算下可以知道能预处理出来一段长度为n的可以包含前导0的数据的所有0的个数,我本来想的是用f(p,m,isf)表示当前是第p个数字,最大为m然后是否为上限isf表示状态,但是写着写着发现不用这么来。。。。所以其实到最后程序里的isf就没有用(在发现这一点的时候我就该想到其实不用这么“dp“),把当前位为0特判一下加上后面的所有可能数字(这个也可以预处理),算完当前这一位之后往下一位继续算。。。最后由于我在f里面的枚举都是从0开始,所以等于说算出来的是”可以包含前导0的数的0的个数“,所以在cal里面还要减去所有的前导0的个数。。。麻烦一批

再说dalao们的做法:其实这个前导0的问题很容易解决。。。从后往前算就ok了,每次算到一位的时候判断是不是0,不是0的话,可以想到当前位为0的话总共出现的次数是容易计算的:把整个数字从这个点分开成左右两段(不包括当前这一位),那么左边的数字*10^(右边的位数),如果当前为0那就不能这么算了(跟数位dp一个道理,isf的时候不能当成所有的情况来做),但是仍然很简单:只要左边不是最大的那个数字,右边仍然可以取到所以情况,所以这时候把左边-1乘上右边的10幂,再加上右边所有的本身的上限就行了。。。还是看代码比较好说。

继续阅读“[数位DP][组合数学][整数分段] UVa 11038 How Many O’s?”

[CF][补题][递推计数][DP] codeforces 1043F Make It One

其实我用了一种操蛋的贪心试了一下,所有的cf测试数据里只有一组会错。。但是还没有搞明白为什么错了,也没有办法再继续证明正确性,所以还是放弃了去看tutorial,发现果然没思路就是dp。。。

然后这又不是一个正常的dp,甚至可以说不算是dp吧。。要从一堆数字里选出来一个集合使得gcd为1。确实,涉及到集合就很难操作。但是可以发现,如果这个集合存在,他的size是很小的,这里可以作为一个突破点去想。如果考虑枚举集合的大小,是否能有简单的计算方法。现在需要求的东西可以转化为,是否存在至少一个集合使得他的size为i然后gcd为1,当然这个也不好直接算,但如果再加一维,再枚举gcd,看看会不会有进展:这时候要求的转化为,是否存在至少一个集合,size为i,gcd为j。可以设一个dp[i][j]表示这种集合的数量,然后尝试是否可以递推。这时候可以发现这i个数字一定是从j的倍数里选出来的,所有的选法有C(cntj,i)种,其中cntj是原数列中j的倍数的数量。而这些里面又有一些不符合要求的,是因为他们的gcd=k*j,然后可以发现这些不符合要求的数量就是dp[i][k*j],这就实现了从大问题往小问题推的转移了。。。然后就只剩下边界的问题了,这个边界也很有意思:因为只考虑k*j<=max(ai)的gcd,所以大于的就是0就可以了

继续阅读“[CF][补题][递推计数][DP] codeforces 1043F Make It One”

[DP][转化目标] UVa 1289 Stacking Plates

附上一个讲的很好的链接https://blog.csdn.net/hao_zong_yin/article/details/79807322

第一感觉是类似矩阵连乘的那种操作,写完了才意识到复杂度会是2500^3,然后果断tle了(Final的题怎么会这么简单)。然后就没有什么太好的思路了。看了题解才有点明白。

这个题第一个难点在于,他又有分割又有合并,同时考虑这两种操作的话会很难设计状态转移,但是其实可以发现这两种操作的数量是有联系的,因为最初的堆数量是确定的,最后的堆数为1,所以分割和合并的数量关系可以确定出来,这样的话只需要算出来其中一种操作的数量就可以了,我这里考虑的是合并的次数w,经过推导可以得出最后答案ans与w的关系是 ans=2*w+n-1;(这个东西其实可以很简单的算出来:直接把每一摞盘子全到一起,总共的join次数为n-1,split次数为0;然后,每次在某一摞盘子内部进行一次split操作,则必然会在最后的结果中引入一次join操作,有一一对应的关系,因此可以推出来对于任意情况都有join次数==split次数+n-1)

第二个难点就是确定了要求合并的次数之后,如何进行dp。这里我们可以借鉴汉诺塔的思想,在考虑前i个(从小到大)盘子的时候,可以把大于i的盘子当成没有一样。而由于这里我关心的只是合并次数,所以不用考虑盘子的中间态(汉诺塔里盘子只能放在某个轴上,但是这里也可以放在地上),这样的话递推方程就会变得简单了。。。只需要使得dp[i][j]表示前i个盘子全放在第j堆上(想象一下这个画面)的最小操作数(这里要求第j堆必须有i这种盘子,说”这种”是因为离散化了),则转移的时候dp[i][j]一定是从dp[i-1][k]得来,其中1<=k<=n,而这时候又有不同的情况需要讨论 :①j==k,这时候如果有i的堆的数量为1,那么就是第j堆这个(因为我们规定只有j堆有i的时候才往这里转移),那么他就不需要动,直接dp[i][j]=dp[i-1][j];如果有i的堆的数量大于1,那就得先把j堆上的 (1到i-1) 这一坨移走,再把其他cnt[i]-1个i类盘子合并到j堆上,再把移走的 (1到i-1) 那一坨移回来(cnt[i]代表有多少堆含有i这个种类,可以预处理出来),所以总共增加的的操作数是cnt[i]-1+1=cnt[i],也就是这里的方程为dp[i][j]=min(dp[i-1][k]+cnt[i]);     ②  j!=k  ,这时候好说,只需要考虑第k堆有没有i就可以了,如果有那就多了cnt[i]-1次操作,如果没有就多了cnt[i]-1+1次操作(注意约定是j堆一定有一个才能往那儿转移,所以除了那一堆里的那个i,还剩下cnt[i]-1个i)。

其他的也就是离散化的操作需要谨慎一点,我由于写错这个wa了两发。。。去重的时候先保留能保留的再去重!不然有可能导致数组扫描完了却没有存任何一个数(比如整个数组都是同一个数)

 

更:今天起床看了看2个月之前做的这个题,觉得当时还是naive,每次直接考虑只向含有第i种盘子的摞转移就好了,于是重写了第二种代码(其实核心思想完全一样的)

继续阅读“[DP][转化目标] UVa 1289 Stacking Plates”