转移自老blog

cf517D

链接

题意

        给你一个字符矩阵,起点在左上角,终点在右下角,每次可以向右或者向下走,最多可以改变这个字符矩阵中的k个字符,使得这个路径构成的字符串字典序最小。矩阵n*n,1≤n≤2000,0≤k≤n^2

题解

        贪心,改完之后肯定是至少前k个都为'a',然后我们dp[i][j],处理出每一个起点走到每一个(i,j)的路线上最多会经过多少个'a',然后,对于每个满足dp[i][j]+k>=i+j-1的点(i,j),构建函数f(i,j)=min(i+j-1,dp[i][j]+k),表示到达点(i,j)最长会经过的全部都是'a'的前缀的长度,取出最大的几个点,然后bfs再处理这些点到终点的的路径,取出字典序最小的,和前面的前缀组合就是答案的方案了。