SRM512 Div1 Easy - MysteriousRestaurant
問題
レストランがn日だけ営業する レストラン利用客は以下のルールを課される
1) 1日1つの料理だけ買える
2) i日目にタイプjの料理を買った場合、i+7日目は同じタイプjの料理しか買えない
3) 何も買わない日があるとその後二度と買えない
i日目のタイプjの料理の値段と所持金が与えられ、このレストランで最大で何日食事できるか求める
解法
d日食事すると決めるとそのために必要な最小の金額sは全探索で求められる
sが所持金b以下になるようなdの最大値を求めればいい
実装
まずは何故かstringで与えられる食事の値段をintに変換する
その後dを大きい方から試していく
ルール2より、日数を7で割った余りが同じ日には同じタイプの食事を買わないといけないから、i%7の値で分けて全タイプ試して最小を取っていく
class MysteriousRestaurant { public: int maxDays(vector<string> p, int b) { vector<int> x[50]; int m = p[0].size(); each(i,p) rep(j,m) { if (isdigit(i[j])) x[j].push_back(i[j]-'0'); else if ('A'<=i[j] && i[j]<='Z') x[j].push_back(10 + i[j]-'A'); else x[j].push_back(36 + i[j]-'a'); } int n = p.size(); for (int d=n; d>=0; --d) { int s = 0; rep(i,7) { int mn = inf; rep(j,m) { int t = 0; for (int k=i; k<d; k+=7) t += x[j][k]; chmin(mn, t); } s += mn; } if (s<=b) return d; } return -1; } };