問題
http://community.topcoder.com/stat?c=problem_statement&pm=12396&rd=15571
・与えられた長方形の地面を平らにしたい。
・地面はセルで区別されており、それぞれのセルの現在の高さがわかっている。
・高さを変化させるには、変化させた高さの分の労力がかかる。
・全てのセルの高さをそれぞれが高々１以下の差にしたいとき、
必要な最小の労力を求める。
解き方
・高さは０～９の９通り。
・このうち、高さの差が高々１になる場合は、
ならした後の高さは（０，１）、（１，２）・・・（８，９）の８通り。
・よって、それぞれの高さにするときに必要な労力をそれぞれ求め、そのうち最小のものが
答えになる。
コード
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()
class HouseBuilding {
public: int getMinimum(vector<string> area) {
int ret=1e+9;
int h=area.size(),w=area[0].size();
FORE(i,0,9){
int tmp=0;
FORE(j,0,h)FORE(k,0,w){
tmp+=min(abs(area[j][k]-'0'-i),abs(area[j][k]-'0'-(i+1)));
}
ret=min(ret,tmp);
}
return ret;
}
};
#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()
class HouseBuilding {
public: int getMinimum(vector<string> area) {
int ret=1e+9;
int h=area.size(),w=area[0].size();
FORE(i,0,9){
int tmp=0;
FORE(j,0,h)FORE(k,0,w){
tmp+=min(abs(area[j][k]-'0'-i),abs(area[j][k]-'0'-(i+1)));
}
ret=min(ret,tmp);
}
return ret;
}
};
Share this
Related Posts
2010 TCO Qualification Round 1 - GirlsAndBoys
問題
http://community.topcoder.com/stat?c=problem_statement&pm=7794&rd=14294
・男の子と女の子が並んでいる。
・このうち、男の子と女の子が隣- SRM 576 DIV1 Easy - ArcadeManao
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12504&rd=15496
解き方
各はしごの数について昇順で調べることができる
- SRM 453 DIV1 Easy - TheBasketballDivOne
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10687&rd=13907
解き方
全探索可能。
DFSを用いて各チームの勝ち負
- SRM 379 DIV1 Easy - SellingProducts
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8440&rd=10800
解き方
一見すべての価格について調べる必要があり、10