SRM 636 DIV1 Easy - ChocolateDividingEasy (×)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=13497&rd=16079

1*1のセルが組み合わされた長方形のチョコレートケーキがある。
各セルごとにおいしさの値が与えられる。

このケーキを横に2つ、縦に2つ切って9つにわける。
このとき、分けたかけらのうちの最小のおいしさの値が最大となる値を求める。


解き方


・計算量の見積もりを誤ってしまった。
・縦に2つ、横に2つなので50C2*50C2=1.5*10^6ぐらい。
・分けたときの各かけらの値を累積和の差として求めれば間に合う。

コード


using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

int b[100][100];
int f[100][100];

class ChocolateDividingEasy {

public: int findBest(vector<string> chocolate) {
int n=chocolate.size();
int m=chocolate[0].size();


FORE(i,1,n+1)FORE(j,1,m+1)b[i][j]=chocolate[i-1][j-1]-'0';
FORE(i,0,n+1)FORE(j,0,m+1){
if(i==0||j==0)f[i][j]=0;
else{
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+b[i][j];
}
}

int ret=0;
FORE(ia,1,n)FORE(ib,ia+1,n)FORE(ja,1,m)FORE(jb,ja+1,m){
int is[4],js[4];
is[0]=0,is[1]=ia,is[2]=ib,is[3]=n;
js[0]=0,js[1]=ja,js[2]=jb,js[3]=m;
int tmp=1e+9;
FORE(i,1,4)FORE(j,1,4){
tmp=min(tmp,f[is[i]][js[j]]-f[is[i]][js[j-1]]-f[is[i-1]][js[j]]+f[is[i-1]][js[j-1]]);
}
ret=max(ret,tmp);
}

return ret;
}

};
このエントリーをはてなブックマークに追加