Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Tallest Billboard

Problem (yeniden ifade)

Her çubuğu sol desteğe, sağ desteğe veya hiçbirine ata. Destekler eşit yükseklikte bitmeli. O yüksekliği büyüt (imkânsızsa 0). n ≤ 20.

Sezgi

Eşit destek ⇔ aynı toplamlı iki ayrık alt küme. 3^n sıkışık; MITM her yarıda 3^{n/2} atama sayar, farklar iptal olunca birleştirir.

Yaklaşımlar

Ortada buluş, 3 yönlü farklar

Doğrulanmadı

Zaman O(n·3^{n/2})Alan O(3^{n/2})

Fikir. Çubukları böl. Her yarı diff = sol − sağ → max sol yükseklik eşler (atla / sola koy / sağa koy). d ile −d birleşir; yükseklik h1 + h2. Her fark için yalnızca en iyi yüksekliği tut.

Yürüyüş. [1,2,3,6] → 6 (1+2+3 vs 6). [1,2,3,4,5,6] → 10. [1,2] → 0.

Trade-off. sum üzerinde knapsack de olur (n·Σ²) çünkü çubuklar küçük (≤ 1000); MITM değer büyüklüğüne bağlı değil.

Çözüm

export function tallestBillboard(rods: number[]): number {
  const mid = rods.length >> 1;

  const diffs = (arr: number[]): Map<number, number> => {
    let dp = new Map<number, number>([[0, 0]]);
    for (const x of arr) {
      const ndp = new Map(dp);
      for (const [d, h] of dp) {
        const left = d + x;
        ndp.set(left, Math.max(ndp.get(left) ?? 0, h + x));
        const right = d - x;
        ndp.set(right, Math.max(ndp.get(right) ?? 0, h));
      }
      dp = ndp;
    }
    return dp;
  };

  const left = diffs(rods.slice(0, mid));
  const right = diffs(rods.slice(mid));
  let ans = 0;
  for (const [d, h] of left) {
    if (right.has(-d)) ans = Math.max(ans, h + right.get(-d)!);
  }
  return ans;
}

export function tallestBillboard(rods: number[]): number {
  const mid = rods.length >> 1;

  const diffs = (arr: number[]): Map<number, number> => {
    let dp = new Map<number, number>([[0, 0]]);
    for (const x of arr) {
      const ndp = new Map(dp);
      for (const [d, h] of dp) {
        const left = d + x;
        ndp.set(left, Math.max(ndp.get(left) ?? 0, h + x));
        const right = d - x;
        ndp.set(right, Math.max(ndp.get(right) ?? 0, h));
      }
      dp = ndp;
    }
    return dp;
  };

  const left = diffs(rods.slice(0, mid));
  const right = diffs(rods.slice(mid));
  let ans = 0;
  for (const [d, h] of left) {
    if (right.has(-d)) ans = Math.max(ans, h + right.get(-d)!);
  }
  return ans;
}

Şablon bağlantısı

Kısıt-doyurma MITM: birleşim anahtarı alt küme toplamı değil işaretli yükseklik farkı.

Yansıma

Çubukları iki yarıya böl. Her çubuk sola, sağa veya hiç. Fark sol − sağ. d ile −d birleşir, yükseklik toplanır.
Her fark için en iyi yüksekliği tut. İki yarı da çubuk kullanmadan fark 0 verirse yükseklik 0’dır; bu bir billboard sayılmaz.
n yaklaşık 20. Her yarı 3^(n/2). [1,2] cevap 0.