Вот еще одна попытка динамического программирования, немного отличающаяся от попытки Георгия Герганова, хотя идея его попытки сформулировать динамическую программу могла быть вдохновлена его ответом.Ни реализация, ни концепция не гарантированно звучат, но я включил набросок кода с наглядным примером:)
Пространство поиска в этом случае зависит не от общей ширины блока, а от количестваинтервалы.Это O(N * n^2) время и O(N * n) пространство, где N и n являются целью и заданным количеством (зеленых) интервалов, соответственно, потому что мы предполагаем, что любой вновь выбранный зеленый интервал должен быть ограничен двумя зелеными интервалами (вместо произвольного расширения на задний план).
Идея также использует идею суммы префиксов, используемую для вычисления прогонов с мажоритарным элементом.Мы добавляем 1, когда видим целевой элемент (в данном случае зеленый) и вычитаем 1 для других (этот алгоритм также поддается нескольким элементам с параллельным отслеживанием суммы префикса).(Я не уверен, что ограничение возможных интервалов для секций с большинством целевого цвета всегда оправдано, но это может быть полезной эвристикой в зависимости от желаемого результата. Она также настраивается - мы можем легко настроить ее для проверки другогочасть, чем 1/2.)
Там, где программа Георгия Герганова стремится минимизировать, эта динамическая программа стремится максимизировать два отношения.Пусть h(i, k) представляет лучшую последовательность зеленых интервалов вплоть до i-го заданного интервала, используя k интервалы, где каждому разрешено простираться назад к левому краю некоторого предыдущего зеленого интервала.Мы предполагаем, что
h(i, k) = max(r + C*r1 + h(i-l, k-1))
, где в текущем интервале кандидатов r - это отношение зеленого цвета к длине отрезка, а r1 - это отношение зеленого к общему количеству данного зеленого.r1 умножается на регулируемую константу, чтобы придать больший вес объему зеленого цвета.l - длина участка.
Код JavaScript (для отладки он включает некоторые дополнительные переменные и строки журнала):
function rnd(n, d=2){
let m = Math.pow(10,d)
return Math.round(m*n) / m;
}
function f(A, N, C){
let ps = [[0,0]];
let psBG = [0];
let totalG = 0;
A.unshift([0,0]);
for (let i=1; i<A.length; i++){
let [l,r,c] = A[i];
if (c == 'g'){
totalG += r - l;
let prevI = ps[ps.length-1][1];
let d = l - A[prevI][1];
let prevS = ps[ps.length-1][0];
ps.push(
[prevS - d, i, 'l'],
[prevS - d + r - l, i, 'r']
);
psBG[i] = psBG[i-1];
} else {
psBG[i] = psBG[i-1] + r - l;
}
}
//console.log(JSON.stringify(A));
//console.log('');
//console.log(JSON.stringify(ps));
//console.log('');
//console.log(JSON.stringify(psBG));
let m = new Array(N + 1);
m[0] = new Array((ps.length >> 1) + 1);
for (let i=0; i<m[0].length; i++)
m[0][i] = [0,0];
// for each in N
for (let i=1; i<=N; i++){
m[i] = new Array((ps.length >> 1) + 1);
for (let ii=0; ii<m[0].length; ii++)
m[i][ii] = [0,0];
// for each interval
for (let j=i; j<m[0].length; j++){
m[i][j] = m[i][j-1];
for (let k=j; k>i-1; k--){
// our anchors are the right
// side of each interval, k's are the left
let jj = 2*j;
let kk = 2*k - 1;
// positive means green
// is a majority
if (ps[jj][0] - ps[kk][0] > 0){
let bg = psBG[ps[jj][1]] - psBG[ps[kk][1]];
let s = A[ps[jj][1]][1] - A[ps[kk][1]][0] - bg;
let r = s / (bg + s);
let r1 = C * s / totalG;
let candidate = r + r1 + m[i-1][j-1][0];
if (candidate > m[i][j][0]){
m[i][j] = [
candidate,
ps[kk][1] + ',' + ps[jj][1],
bg, s, r, r1,k,m[i-1][j-1][0]
];
}
}
}
}
}
/*
for (row of m)
console.log(JSON.stringify(
row.map(l => l.map(x => typeof x != 'number' ? x : rnd(x)))));
*/
let result = new Array(N);
let j = m[0].length - 1;
for (let i=N; i>0; i--){
let [_,idxs,w,x,y,z,k] = m[i][j];
let [l,r] = idxs.split(',');
result[i-1] = [A[l][0], A[r][1], 'g'];
j = k - 1;
}
return result;
}
function show(A, last){
if (last[1] != A[A.length-1])
A.push(last);
let s = '';
let j;
for (let i=A.length-1; i>=0; i--){
let [l, r, c] = A[i];
let cc = c == 'g' ? 'X' : '.';
for (let j=r-1; j>=l; j--)
s = cc + s;
if (i > 0)
for (let j=l-1; j>=A[i-1][1]; j--)
s = '.' + s
}
for (let j=A[0][0]-1; j>=0; j--)
s = '.' + s
console.log(s);
return s;
}
function g(A, N, C){
const ts = f(A, N, C);
//console.log(JSON.stringify(ts));
show(A, A[A.length-1]);
show(ts, A[A.length-1]);
}
var a = [
[0,5,'b'],
[5,9,'g'],
[9,10,'b'],
[10,15,'g'],
[15,40,'b'],
[40,41,'g'],
[41,43,'b'],
[43,44,'g'],
[44,45,'b'],
[45,46,'g'],
[46,55,'b'],
[55,65,'g'],
[65,100,'b']
];
// (input, N, C)
g(a, 2, 2);
console.log('');
g(a, 3, 2);
console.log('');
g(a, 4, 2);
console.log('');
g(a, 4, 5);