SRM 247 DIV1 Hard Necklaces
問題
輪になったネックレスがある。
ネックレスの各宝石の価値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; } };