問題
http://community.topcoder.com/stat?c=problem_statement&pm=11295&rd=14537
解き方
何日目まで訪れることができるかを固定することで貪欲法で解くことができる。
N日目まで訪れるとすると、１日目＋７の倍数・・・６日目＋７の倍数のそれぞれについて
一番コストの少ない種類の和をとり、それが予算以下であれば
N日目まで訪れることができる。
コード
class MysteriousRestaurant {
public:
int calc(char ch){
if('A'<=ch && ch<='Z')return ch-'A'+10;
if('a'<=ch && ch<='z')return ch-'a'+36;
return ch-'0';
}
int maxDays(vector<string> prices, int budget) {
int n=prices.size(),m=prices[0].size();
int ret=0;
FORE(i,0,n){
int cost=0;
for(int j=0;j<7&&j<=i;j++){
int sum=1e+9;
for(int k=0;k<m;k++){
int tmp=0;
for(int l=j;l<=i;l+=7)tmp+=calc(prices[l][k]);
sum=min(sum,tmp);
}
cost+=sum;
}
if(cost<=budget)ret=max(ret,i+1);
}
return ret;
}
};
public:
int calc(char ch){
if('A'<=ch && ch<='Z')return ch-'A'+10;
if('a'<=ch && ch<='z')return ch-'a'+36;
return ch-'0';
}
int maxDays(vector<string> prices, int budget) {
int n=prices.size(),m=prices[0].size();
int ret=0;
FORE(i,0,n){
int cost=0;
for(int j=0;j<7&&j<=i;j++){
int sum=1e+9;
for(int k=0;k<m;k++){
int tmp=0;
for(int l=j;l<=i;l+=7)tmp+=calc(prices[l][k]);
sum=min(sum,tmp);
}
cost+=sum;
}
if(cost<=budget)ret=max(ret,i+1);
}
return ret;
}
};