hihocoder 1580 枚举 dp RMQ

题意：

题目链接：http://hihocoder.com/problemset/problem/1580?sid=1195305

给出一个矩阵，让你将其中一个数的值变成p（必须修改一个，且仅能修改一个），然后求最大子矩阵和。

思路：

2017北京网络赛C题，这题最后没A真是好气啊。

一开始被带偏榜，花了太多时间在D上，结果一直wa，后来C题过得多了再来看C题，秒出思路，然后一直WA到结束。

只不过是在最大子矩阵上加了一个修改，同样是枚举行x和行y作为子矩阵的上下边界，然后对这两行做差，得到一个序列，对这个序列一遍dp，求最大子段和即可。至于修改操作，当x和y确定了，肯定对于第j列在[x,y]之间找最小的数变成P（这样贡献最大），这点利用RMQ就行，然后设dp[i][0/1]分别表示到第i个数已经修改或者没修改的最大值，dp一下即可。

trick在于，修改的点不一定在子矩阵内的，当时懵逼只考虑了修改的点在子矩阵左边，其实也有可能在右边，甚至可能根本就不在枚举的x行到y行之间，需要分情况讨论，另外要注意常数，o(N^3)，写挫就T了。

代码： #include #include #include #include #include using namespace std;const int MAXN = 305;const int INF = 0x3f3f3f3f;int a[MAXN][MAXN], col[MAXN][MAXN], C[MAXN][MAXN][20];void ST(int id, int n) { for (int i = 1; i