SRM 487 250pt : BunnyComputer
問題概要
正整数列Xが与えられる。i番目とi+k+1番目をペアでとることができる。重複してとることはできない。とることのできる最大スコアを求める問題。
解法
MOD k+1で考えてよい。配列をMOD k+1で分類したとき、長さが偶数なら全部とることができて、奇数なら偶数番目で最小のものを除いて全て取ることができる。
計算量O(N*K)。
acceptされたコード
#include <vector> using namespace std; const int INF = 1<<29; struct BunnyComputer { int getMaximum(vector <int> preference, int k) { const int N = preference.size(); int ans = 0; for(int m=0; m<=k; m++){ int total = 0, mini = INF, cnt = 0; for(int i=0; i<N; i++)if(i%(k+1) == m){ cnt++; total += preference[i]; if(preference[i] < mini && cnt % 2 == 1){ mini = preference[i]; } } if(cnt % 2 == 0){ ans += total; } else{ ans += total - mini; } } return ans; } };