問題
http://community.topcoder.com/stat?c=problem_statement&pm=10719&rd=14179
解き方
ｄｐを利用して、ある長方形を考えた時
その内部にある長方形のうち最大のものか、
それより内部にある長方形＋現在の長方形のうち最大のものを求めていく。
コード
int dp[55][55][55][55];
class DonutsOnTheGridEasy {
public:
int calc(vector<string> grid) {
int h=grid.size(),w=grid[0].size();
memset(dp,0,sizeof(dp));
for(int hh=3;hh<=h;hh++)for(int ww=3;ww<=w;ww++){
for(int i=0;i+hh-1<h;i++)for(int j=0;j+ww-1<w;j++){
int u=i+hh-1,v=j+ww-1;
int ok=1;
FORE(k,0,ww){
if(grid[i][j+k]!='0' || grid[u][j+k]!='0')ok=0;
}
FORE(k,0,hh){
if(grid[i+k][j]!='0' || grid[i+k][v]!='0')ok=0;
}
dp[i][j][u][v]=ok;
dp[i][j][u][v]=max(dp[i][j][u][v],dp[i+1][j][u][v]);
dp[i][j][u][v]=max(dp[i][j][u][v],dp[i][j+1][u][v]);
dp[i][j][u][v]=max(dp[i][j][u][v],dp[i][j][u-1][v]);
dp[i][j][u][v]=max(dp[i][j][u][v],dp[i][j][u][v-1]);
dp[i][j][u][v]=max(dp[i][j][u][v],dp[i+1][j+1][u-1][v-1]+ok);
}
}
return dp[0][0][h-1][w-1];
}
};
class DonutsOnTheGridEasy {
public:
int calc(vector<string> grid) {
int h=grid.size(),w=grid[0].size();
memset(dp,0,sizeof(dp));
for(int hh=3;hh<=h;hh++)for(int ww=3;ww<=w;ww++){
for(int i=0;i+hh-1<h;i++)for(int j=0;j+ww-1<w;j++){
int u=i+hh-1,v=j+ww-1;
int ok=1;
FORE(k,0,ww){
if(grid[i][j+k]!='0' || grid[u][j+k]!='0')ok=0;
}
FORE(k,0,hh){
if(grid[i+k][j]!='0' || grid[i+k][v]!='0')ok=0;
}
dp[i][j][u][v]=ok;
dp[i][j][u][v]=max(dp[i][j][u][v],dp[i+1][j][u][v]);
dp[i][j][u][v]=max(dp[i][j][u][v],dp[i][j+1][u][v]);
dp[i][j][u][v]=max(dp[i][j][u][v],dp[i][j][u-1][v]);
dp[i][j][u][v]=max(dp[i][j][u][v],dp[i][j][u][v-1]);
dp[i][j][u][v]=max(dp[i][j][u][v],dp[i+1][j+1][u-1][v-1]+ok);
}
}
return dp[0][0][h-1][w-1];
}
};