SRM596 IE
概要
あるn個の要素 vector<int> desiredArray が与えられている.
要素の値が0となるn個の要素を以下の操作を繰り返すことで,desiredArray と一致させるための最小回数を求めたい.
- ある要素を+1する
- すべての要素を2倍する
制約条件
- 1 <= n <= 50
- 1 <= desiredArray[i] <= 1000
考えたこと
数 val になるように+1 や *2 した最小回数を f(val) とする.
この最小回数となる方法が複数存在する場合は,*2倍の回数が多いやり方がより最適な解とする.
(*2なら他の要素の回数も減らせる可能性があって効率がいいから.)
この事をn個の要素に対して行い,
- 2倍する最大の回数 max_dbl と
- +1 した回数の総数 sum_inc
の和を答えとする.
コード
#define INF (1<<29) #define MOD 7777 int dp[1050]; // target value => (number of increment, number of double) class IncrementAndDoubling { public: int f(int val) { if (val == 0) return 0; if (dp[val] != -1) return dp[val]; int res = f(val-1) + MOD; if (val % 2 == 0) { res = min(res, f(val / 2) + 1); } return (dp[val] = res); } int getMin(vector <int> desiredArray) { for (int i = 0; i < 1050; ++i) dp[i] = -1; int n = desiredArray.size(); int sum_inc = 0; int max_dbl = 0; for (int i = 0; i < n; ++i) { int inc_dbl_pair = f(desiredArray[i]); sum_inc += inc_dbl_pair / MOD; max_dbl = max(max_dbl, inc_dbl_pair % MOD); } return sum_inc + max_dbl; } }