C
|
Optimal
Segments
Input: Standard Input
Output: Standard Output
|

|
Consider a grid of size 1 x
N.
Each cell of the grid has the following properties
·
Cell C of
the grid has a value of VC (1 ≤ C ≤
N)
·
The value
of each cell is a positive integer less than 26
·
Some of the
cells are special and they are represented with the character X
·
Cell C has
a weight of
(two to the power of cell value)
·
The special
cells have weights of 1
You
will be given the values of these N cells and your job will be to divide these
into K segments so that
·
Each segment contains
at least one cell
·
There is at
least one special cell in each segment
The weight of a segment is equal to the
product of the weights of the cells it contains. You have to form segments in
such a way so that ratio
(Highest weight of all the segments) /
(Lowest weight of all the segments) is minimized.
In case there are multiple answers with the
same lowest ratio, you have to make sure the number of cells in the first
segment is maximized. If there is still a tie, then make sure the number of
cells in the second segment is maximized and so on.
Example:
N = 5 and K = 2
Cell values = {1 2 X 3 X }
Cell weights = {2 4 1 8 1}
Optimal segmentation = (2 4 1)(8 1)
Weights of segments = (8)(8)
Ratio = 1
Final Result = (1 2 X)(3 X)
Input
The first line of input is an integer T(T ≤
200) that indicates
the number of test cases. Each case starts with two integers N(1
< N < 31) and K(1 < K < 16). The meaning of N and K are mentioned
above. The next line contains N integers where the Ith integer gives the
value of VI. The integers that are special will be represented by
X.
Output
For each case, output the case number first.
If there is no way to divide the N cells into K segments, meeting
the constraints above, then print “not possible!” If there is a way
but the ratio is greater than 1015 then print “overflow”. If the ratio is
not greater than 1015 then output the ratio first followed by the
segmentations. Each segment is enclosed by brackets. Look at the output for
detailed format.
Sample Input Output for Sample
Input
4
5 2
1 2 X 3 X
6 3
X X 2 3 4 5
10 3
X X X 25 25 25 25 25 25 25
10 3
4 X 3 1 X 3 X X 3 2 |
Case 1: 1 (1 2 X)(3 X)
Case 2: not possible!
Case 3: overflow
Case 4: 8 (4 X 3)(1 X 3
X)(X 3 2)
|
Problemsetter:
Sohel Hafiz
Special
Thanks: Md.
Arifuzzaman Arif
題目描述:
將 N 個數字分成 K 段,每一段都要包含一個 X。
求分段後,抓每一段的最大值 - 最小值最小化 (最小化最大差額)。
最後要輸出解的分法,按照字典順序,越左邊的段個數越多越好。
題目解法:
狀��� dp[i][j][k] 討論前 i 個,切成 j 段,其中最小值為 k 的最小最大值為何。
最麻煩就是輸出解法了,字典順序搞了好久才找到輸出的方法。
#include <stdio.h>
#include <string.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int V[35], N, K;
int dp[31][16][30*26 + 5]; // [i-th][segment_count][min_value]
int ac_dp[31][16][30*26 + 5];
void solve() {
int i, j, k, prev;
int sum[35] = {}, sumX[35] = {}, nextX[35] = {};
for(i = 1; i <= N; i++) {
sum[i] = sum[i-1] + V[i];
sumX[i] = sumX[i-1] + (V[i] == 0);
}
for(i = N, prev = N+1; i >= 0; i--) {
nextX[i] = prev;
if(V[i] == 0)
prev = i;
}
if(sumX[N] < K) {
puts("not possible!");
return ;
}
set<int> R[31][16];
dp[0][0][0] = 0, R[0][0].insert(0);
for(i = 0; i < N; i++) {
for(j = 0; j < K; j++) {
for(set<int>::iterator it = R[i][j].begin();
it != R[i][j].end(); it++) {
for(k = nextX[i]; k <= N; k++) {
int s = sum[k] - sum[i];
int mn = min(*it, s), mx = max(dp[i][j][*it], s);
if(i == 0) mn = mx = s;
if(R[k][j+1].find(mn) == R[k][j+1].end())
R[k][j+1].insert(mn), dp[k][j+1][mn] = 0xfffffff, ac_dp[k][j+1][mn] = 0;
dp[k][j+1][mn] = min(dp[k][j+1][mn], mx);
}
}
}
}
int ret = 0xfffffff;
for(set<int>::iterator it = R[N][K].begin();
it != R[N][K].end(); it++) {
ret = min(ret, dp[N][K][*it] - *it);
}
if(ret >= 50) {
puts("overflow");
return;
}
printf("%lld ", 1LL<<ret);
vector< pair<int, int> > P;
for(set<int>::iterator it = R[N][K].begin();
it != R[N][K].end(); it++) {
if(ret == dp[N][K][*it] - *it) {
ac_dp[N][K][*it] = 1;
P.push_back(make_pair(*it, dp[N][K][*it]));
}
}
for(i = N; i >= 0; i--) {
for(j = 0; j < K; j++) {
for(set<int>::iterator it = R[i][j].begin();
it != R[i][j].end(); it++) {
for(k = nextX[i]; k <= N; k++) {
int s = sum[k] - sum[i];
int mn = min(*it, s), mx = max(dp[i][j][*it], s);
if(i == 0) mn = mx = s;
if(ac_dp[k][j+1][mn]) {
int ok = 0;
for(int p = 0; p < P.size(); p++) {
if(*it >= P[p].first && dp[i][j][*it] <= P[p].second)
ok = 1;
}
if(ok) {
ac_dp[i][j][*it] = ok;
break;
}
}
}
}
}
}
int idx = 0, idx_mn = 0;
for(int seg = 0; seg < K; seg++) {
for(j = N; j >= idx; j--) {
if(sumX[j] - sumX[idx] == 0)
continue;
int s = sum[j] - sum[idx];
int mn = min(idx_mn, s), mx = max(dp[idx][seg][idx_mn], s);
if(idx == 0) mn = mx = s;
if(ac_dp[j][seg+1][mn]) {
putchar('(');
for(k = idx+1; k <= j; k++) {
if(V[k])
printf("%d", V[k]);
else
printf("X");
printf("%c", k == j ? ')' : ' ');
}
idx = j, idx_mn = mn;
break;
}
}
}
puts("");
}
int main() {
int testcase, cases = 0;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &N, &K);
for(i = 1; i <= N; i++) {
char s[10];
scanf("%s", s);
if(s[0] == 'X')
V[i] = 0;
else
sscanf(s, "%d", &V[i]);
}
printf("Case %d: ", ++cases);
solve();
}
return 0;
}
/*
1000
20 6
X 3 7 X 2 4 6 3 X 6 9 4 X X 4 7 X X 5 6
20 12
X X 2 X 7 2 X X X X 1 X X 9 X X X X 4 X
*/