这是我们学校某%你赛的一道题,教练讲的没听懂,放在洛谷上来问一下
有一个 nnn 行 nnn 列的01矩阵,给定整数 ddd,你可以修改任意一个 ddd 行 ddd 列的子矩阵,使得子矩阵内的所有位置都变为0,定义 W=∑全为0的行+∑全为0的列W=\sum\text{全为0的行}+\sum\text{全为0的列}W=∑全为0的行+∑全为0的列 求 WmaxW_{max}Wmax
我觉得应该是动态规划,所以整了个O(n2d)\mathcal{O(n^2d)}O(n2d)的,但是n和d都是上千的,只得了60分 求助更优的算法