首先贴出来网上的动态规划正解思路：
这题是HDU 1506 的加强版，定义一个二维数组，d[i][j]表示第i行j列元素在前i行中的最大高度。（以第一行为底）例如测试样例： 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 (F=1,R=0,方便求和） 1 2 2 2 2 2 0 0 0 1 1 1 转化完就是右边矩阵 0 0 0 3 3 3 1 1 1 1 1 1 1 1 1 4 4 4 1 1 1 1 1 1 2 2 2 5 5 5 接下来就和 HDU 1506 一样了，逐行求最大矩形面积。 动态方程：l[j] r[j]分别表示左边界与右边界。（见上一篇：HDU 1506 Largest Rectangle in a Histogram） l[j]=l[l[j]-1]; r[j]=r[r[j]-1];正解链接：http://blog.sina.com.cn/s/blog_6cf509db0100sx1z.html
我的思路：矩形4个边。X1，X2，Y1，Y2。，矩形面积= (Y2-Y1+1)*(X2-X1+1)，
1.若遇到F，且F左边没有F，且本列没有矩形，那么增加一个矩形并加索引
2.若遇到F，且F左边没有F。且本列已有矩形，不需要做什么
3.若遇到F，且F左边有F，那么检查前一列的矩形，如果前一列有本行的新矩形，那么扩大这个矩形，把这个矩形的X2变为当前的X。
4.若遇到F，如果前一列有一个矩形完全覆盖了这个F以及和这个F连续的最左边的F，那么什么都不做，如果前一列没有这种矩形，那么需要建立一个新矩形。并加索引。
5.若遇到R，如果本列有单列的矩形，则计算面积并删除本矩形。若本列恰好为某个矩形的边，则计算该矩形面积，并缩小该矩形。若本列在某个矩形中间的位置。则把矩形拆分为两个矩形，并在第一个矩形中留下指向第二个矩形的指针。因为矩形索引可能很多，所以此处不更新索引。
6.查找索引时，需要校验该矩形是否被拆分，如果发现矩形被拆分，而且当前需要的是拆分后的第二个矩形，甚至有多次拆分，需要的是后面的矩形，那么利用拆分矩形之间的指针找到所需矩形并更新索引。
7.处理完全部数据后，计算所有还没计算面积的矩形的当前面积。
因为做这道题之前就知道是DP，所以写程序时数组起名字写的是DP，写完之后我也不知道我用的是不是动态规划，找了一个网上的动态规划算法提交了一下试试，然后发现我的算法居然比网上算法用时更短。
这题是1506的加强版，但是我两个题解法都跟主流解法不一样。。
这题我根本没想明白就开始敲代码了，敲着敲着发现之前想的根本不对，然后就改，然后发现还不对，再改，改了之后调试发现还不对，然后再加逻辑，最后写了1个多小时，逻辑巨复杂，然后一次就A了。
//pRectangleCount[n]是第n列的矩形数量
//pRectangle[n][x]是第n列的第X个矩形，这个是指针。指向dp
//dp其实是所有的矩形，跟动态规划没关系
#include <stdio.h>
#include <stdlib.h> #include <string.h> typedef struct{ int y1; int x1; int x2; int next; }RECTANGLE; RECTANGLE dp[100000001]; int pRectangle[1001][1001]; int pRectangleCount[1001]; int dpCount; int main() { int i,j,lineStart,l,max,k,m,n; char temp; int x1,x2,y1; int flag; int maxtemp; scanf("%d", &k); while(k--) { scanf("%d%d", &m, &n); max = 0; memset(pRectangleCount, 0, sizeof(pRectangleCount)); dpCount = 0; for(i = 0; i < m; i++) { lineStart = -1; for(j = 0; j < n; j++) { scanf("%c", &temp); if(temp == 'F') { if(lineStart == -1 && pRectangleCount[j] == 0) { dp[dpCount].y1 = i; dp[dpCount].x1 = j; dp[dpCount].x2 = j; dp[dpCount].next = 0; lineStart = j; pRectangle[j][pRectangleCount[j]] = dpCount; dpCount++; pRectangleCount[j]++; } else if(lineStart == -1) { lineStart = j; } else if(lineStart != -1) { flag = 0; for(l=0;l < pRectangleCount[j - 1];l++) { if(dp[pRectangle[j-1][l]].y1 == i) { dp[pRectangle[j-1][l]].x2 = j; pRectangle[j][pRectangleCount[j]] = pRectangle[j-1][l]; pRectangleCount[j]++; flag = 1; } else if(dp[pRectangle[j-1][l]].x1 >= lineStart) { flag = 1; } } if(flag == 0) { dp[dpCount].y1 = i; dp[dpCount].x1 = lineStart; dp[dpCount].x2 = j; dp[dpCount].next = 0; for(l=lineStart;l<=j;l++) { pRectangle[l][pRectangleCount[l]] = dpCount; pRectangleCount[l]++; } dpCount++; } } } else if(temp == 'R') { for(l=0;l < pRectangleCount[j];l++) { x2 = dp[pRectangle[j][l]].x2; while(x2 < j) { pRectangle[j][l] = dp[pRectangle[j][l]].next; x2 = dp[pRectangle[j][l]].x2; } y1 = dp[pRectangle[j][l]].y1; x1 = dp[pRectangle[j][l]].x1; if(x1 == j && x2 == j) { maxtemp = (x2 - x1 + 1) * (i - y1); if(maxtemp > max) max = maxtemp; } else if(x1 == j) { maxtemp = (x2 - x1 + 1) * (i - y1); if(maxtemp > max) max = maxtemp; dp[pRectangle[j][l]].x1 = j + 1; } else if(x2 == j) { maxtemp = (x2 - x1 + 1) * (i - y1); if(maxtemp > max) max = maxtemp; dp[pRectangle[j][l]].x2 = j - 1; } else { maxtemp = (x2 - x1 + 1) * (i - y1); if(maxtemp > max) max = maxtemp; dp[dpCount].y1 = y1; dp[dpCount].x1 = j + 1; dp[dpCount].x2 = x2; dp[dpCount].next = 0; dp[pRectangle[j][l]].x2 = j - 1; dp[pRectangle[j][l]].next = dpCount; dpCount++; } } pRectangleCount[j] = 0; lineStart = -1; } else { j--; } } } for(i = 0; i < m; i++) { for(j = 0; j < n; j++) { for(l=0;l < pRectangleCount[j];l++) { x2 = dp[pRectangle[j][l]].x2; while(x2 < j) { pRectangle[j][l] = dp[pRectangle[j][l]].next; x2 = dp[pRectangle[j][l]].x2; } y1 = dp[pRectangle[j][l]].y1; x1 = dp[pRectangle[j][l]].x1; maxtemp = (x2 - x1 + 1) * (i - y1 + 1); if(maxtemp > max) max = maxtemp; } } } printf("%d\n", max * 3); } return 0; }