(DP)太菜了，开个随笔稍微记录一下
挺经典一题
(f[l][r][0/1])表示关掉([l,r])内的路灯后在左侧还是右侧
然后转移方程
(f[l][r][0]=min(f[l+1][r][0]+d[l][l+1]*(s[n]-s[r]+s[l]),f[l+1][r][1]+d[l][r]*(s[n]-s[r]+s[l])))
(f[l][r][1]=min(f[l][r-1][0]+d[l][r]*(s[n]-s[r-1]+s[l-1]),f[l][r-1][1]+d[r-1][r]*(s[n]-s[r-1]+s[l-1])))
不能直接背包，因为不知道最后一个(Y)到底有没有子弹
预处理(v[i][j][0/1])表示第(i)列用(j)发子弹，最后一发打在(N/Y)上
也就是说遇到一个(N)上面是(Y)的情况，可以把上面的(Y)压缩到下面的(N)上，用(1)来表示
如果不是这种情况就把(v[i][j][0])和(v[i][j][1])一起用(v[i][j-1][1])更新
设计(f[i][j][0/1])表示前(i)列用(j)发，最后一发是(N/Y)的最大值
然后就可以了，如果枚举哪一列，一共用了几发，这一列用几发
转移要注意的有点多：
(1.f[i][j][1]=max(f[i-1][j-k][1]+v[i][k][1]))
表示如果一直有子弹可以借从别的地方借一个打掉最上面的(Y)再还回去的最大值
(2.if(k) f[i][j][0]=max(f[i-1][j-k][1]+v[i][k][0]))
这个表示从当前列借一发子弹给前面的列，得到的最大结果
(3.if(j>k) f[i][j][0]=max(f[i-1][j-k][0]+v[i][k][1]))
这个表示从前面的某一列借一发给当前列，得到的最大结果
答案是(max(f[m][j][0]))
(f[i][j][k][0/1])表示到(i)位置，有(j)个(0)变成(1)，有(k)个(1)变成(0)，结尾是(0/1)
然后就……(ning)转移，最后取(max{f[n][i][i][0/1]})
就……求出最长的，然后树上模拟？？
然后……数组忘了调大+(sb)错误(WA)了两发
这都能蓝？黄的差不多
问最长严格下降子序列长度，和数值不同的最长严格下降子序列个数
第一问(O(n^2)dp)，第二问我们发现，只要边(dp)边记录次数，然后往前更新答案的时候遇到同样的数字就(break)就行了
(s[i][k])表示在(i)时刻(k)这个位置的前缀和，注意每个时刻机器人位置都变化所以这个前缀和是错位的……
然后就可以得到(O(n^3))的(dp)方程：(f[i]=max{f[i-k]+s[i][j]-s[i-k][(j-k+p*n)\%n]-w[(j-k+p*n)\%n]})
其中(i)是时间，(j)是当前位置，(k)是设定的移动距离
然后卡过了
为了有脸还是优化一下
然后我们变形一下方程得到 (f[i]=max{f[i-k]-s[i-k][(j-k+p*n)\%n]-w[(j-k+p*n)\%n]}+s[i][j])
那单调队列维护一下前面这个(max)里的东西就好了
写起来稍微有点麻烦
先求出(f[l][r])表示([l,r])内能分出多少个单词，只要枚举(r)然后倒推(l)就可以(O(n^2))实现
然后(dp[i][k])表示到(i)分了(k)段的最大答案，注意(k<=i)