SRM 383 DIV1 Easy - Planks

SRM 383 DIV1 Easy - Planks

10:00

問題


http://community.topcoder.com/stat?c=problem_statement&pm=8396&rd=10806

解き方


１つの木の長さを１〜１００００のそれぞれに固定して考える。
あとは、与えられた木がその長さで割った時、値がプラスなら足していき
最大のものを求めれば良い。

コード


class Planks {

public: int makeSimilar(vector<int> lengths, int costPerCut, int woodValue) {
int n=lengths.size();
int ret=0;

for(int len=1;len<=10000;len++){
int cur=0;
FORE(i,0,n)if(len<=lengths[i]){
int num=lengths[i]/len;
int cuts=num-((lengths[i]%len)==0);
int value=num*woodValue*len-cuts*costPerCut;
if(value>0)cur+=value;
}
ret=max(ret,cur);
}

return ret;
}

};

Share this

Google Facebook Twitter More

Related Posts