就说一个bzoj上的dp题 bzoj1057 ： ZJOI2007 棋盘制作
就不粘题面了
第一问大家应该都会做： 预处理一下这个点横向和纵向上连续合法的序列有多长 然后dp一下，f[i][j] 从 f[i-1][j-1] 转移过来，这个应该想想就明白了 复杂度为O（n^2）, 已经最优了→读入复杂度。。。
第二问大部分题解上写的都是悬线法，可惜我不会，我太菜了 不过我用单调栈过了
第一问中预处理过了对于每个点所在该行到这个点为止有多少个连续合法的的点（我语文不好） 这样我们就可以对每一列进行单调栈处理，和poj2559 http://poj.org/problem?id=2559 用的是同样处理的方法。。 当时高二学长写这个题的时候没有写，所以这个题我WA了好多次
单调栈中还要存每个矩形底面的长度，说完单调栈大家应该会写了。。 把这份辣鸡代码留给大家对拍。。。估计您们一遍就过了
#include<bits/stdc++.h> using namespace std; #define FOR(i,s,t) for(int i=(s);i<=(t);i++) inline int read(void){ int x = 0, c, f = 1; do { c = getchar(); if (c=='-') f = -1;}while (c<'0'||c>'9'); do { x = x*10+c-'0';c = getchar();}while(c>='0'&&c<='9'); return x * f; } typedef long long LL; const int N = 2000 + 1000; bool val[N][N]; int f[N][N][2], n, m,dp[N][N]; int sta[N],var[N],stop; LL cnt; inline void calm(void){ int tot = 0; for (int i = 1; i <= stop; i++) tot += var[i]; for (int i = 1; i <= stop; i++) { cnt = max(cnt,(LL)tot * sta[i]); tot -= var[i]; } stop = 0; } void DP(int lie) { stop = 0; for (int i = 1; i <= n; i++) { if (val[i][lie] == val[i-1][lie]) calm(); int tot = 0; while (stop && sta[stop] > f[i][lie][0]) cnt = max(cnt,(LL)sta[stop]* (var[stop] + tot)),tot += var[stop], stop--; if(stop && sta[stop] == f[i][lie][0]) var[stop] += tot + 1, cnt = max(cnt,(LL)sta[stop] * var[stop]); else sta[++stop] = f[i][lie][0], var[stop] = 1 + tot, cnt = max(cnt,(LL)f[i][lie][0] * var[stop]); // if(lie == 3) cout << sta[stop] << " " << var[stop] << endl; } calm(); } int main(){ //freopen("in.txt","r",stdin); //freopen("wa.txt","w",stdout); n = read(), m = read(); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) val[i][j] = read(); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { f[i][j][0] = (val[i][j] ^ val[i][j-1]) ? f[i][j-1][0] + 1 : 1; f[i][j][1] = (val[i][j] ^ val[i-1][j]) ? f[i-1][j][1] + 1 : 1; } int ans = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { dp[i][j] = (val[i][j] == val[i-1][j-1] && f[i][j][0] > dp[i-1][j-1] && f[i][j][1] > dp[i-1][j-1])? dp[i-1][j-1] + 1 : 1; ans = max(ans,dp[i][j]); } for (int i = 1; i <= m; i++) DP(i); cout << (LL)ans * ans << endl << cnt << endl; }