SRM 247 DIV1 Hard Necklaces

問題 Editorial

問題

輪になったネックレスがある。
ネックレスの各宝石の価値gemsが与えられる。
このネックレスをn回カットしてnつに分けたい。
カット後の各部分は1つ以上の宝石が含まれていなければいけない。
カット後の各部分の価値の総和の(最大-最小)を最小化せよ

解答

最小となる部分を全探索する。
そしてその各最小に対して((最小の部分の右から)i番目まで使ったとき * kつに分ける)であって、各部分が最小の価値以上であるときの価値の総和の最大の最小をDPする

コメント

まあ、DP。でも結構賢い感じで良い感じの問題だよね。
解けたいよね

コード

#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef vector<int> vi;
int dp[55][55];
struct Necklaces {
	vi g; int n;
	int mini, left, right;
	int rec(int i, int k) {
		if(dp[i][k] != -1) return dp[i][k];
		if(k == 0) return left + i == right ? 0 : INF;
		int r = INF;
		int sum = 0;
		rer(j, left+i+1, right) {
			sum += g[(j-1)%n];
			if(mini <= sum)
				r = min(r, max(sum, rec(j - left, k - 1)));
		}
		return dp[i][k] = r;
	}
	int inequity(int K, vector <int> gems) {
		if(K == 1) return 0;
		g = gems, n = g.size();
		int r = INF;
		rep(i, n) rer(j, i+1, n+i) {
			mini = 0;
			reu(k, i, j) mini += gems[k % n];
			left = j, right = n + i;
			mset(dp, -1);
			r = min(r, rec(0, K - 1) - mini);
		}
		return r;
	}
};