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;
	}

};