链接

题意

        给你一个字符矩阵，起点在左上角，终点在右下角，每次可以向右或者向下走，最多可以改变这个字符矩阵中的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再处理这些点到终点的的路径，取出字典序最小的，和前面的前缀组合就是答案的方案了。