題目：計算一個01矩陣中有多少個不同的矩形。
分析：動態規劃（DP）。這個題目中使用了多個不同狀態。
定義狀態：s（i，j）為矩形ixj中矩形個數，f（i，j）為矩形ixj中包含塊（i，j）的矩形個數；
轉移方程：s（i，j）= s（i-1，j）+ s（i，j-1）- s（i-1，j-1）+ f（i，j）；
定義狀態：l（i，j）為第i行，第j列的位置前面連續1的個數，即以塊（i，j）結束的最大寬；
轉移方程：f（i，j）= sum（l（i，j）+ min（l（i，j），l（i-1，j））+ ...）；
從下向上統計矩形個數，遇到寬度隨著l變小而縮小；
說明：最近什麼也沒幹╮(╯▽╰)╭。
#include <stdio.h> #include <stdlib.h> #include <string.h> char b[111][111]; int l[111][111]; int f[111][111]; int s[111][111]; int main() { int r, c; while (~scanf("%d",&r) && r) { scanf("%d",&c); for (int i = 1; i <= r; ++ i) { scanf("%s",&b[i][1]); } memset(l, 0, sizeof(l)); for (int i = 1; i <= r; ++ i) { for (int j = 1; j <= c; ++ j) { l[i][j] = (b[i][j]=='1' ? l[i][j-1]+1 : 0); } } memset(f, 0, sizeof(f)); for (int i = 1; i <= r; ++ i) { for (int j = 1; j <= c; ++ j) { int min = 100; for (int k = i; k >= 1; -- k) { if (min > l[k][j]) { min = l[k][j]; } f[i][j] += min; } } } memset(s, 0, sizeof(s)); for (int i = 1; i <= r; ++ i) { for (int j = 1; j <= c; ++ j) { s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + f[i][j]; } } printf("%d\n",s[r][c]); } return 0; }