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

Hardbitmask-dp

Maximize Score After N Operations

Problem (yeniden ifade)

nums uzunluğu 2n (n ≤ 7). k. işlemde (1-indeks) kalan iki sayı x,y seç, k * gcd(x,y) puan al. n işlem sonrası toplamı maksimize et.

Sezgi

n küçük, kullanılan sayı kümesi bitmask. İşlem indeksi kullanılan sayı adedinden gelir: popcount(mask)/2 + 1.

Yaklaşımlar

Çift bitmask DP

Doğrulanmadı

Zaman O(n^2 * 2^n)Alan O(2^n)

Fikir. dp[mask] = mask içindeki sayılarla max skor. Yalnızca çift popcount. Kullanılmamış her (i,j) çiftini dene, op * gcd ekle. gcd tablosunu önceden hesapla.

Yürüyüş. [1,2] → 1. [3,4,6,8] → 11 (önce gcd(3,6), sonra gcd(4,8)). [1,2,3,4,5,6] → 14 (büyük gcd’yi son işleme sakla).

Trade-off. 2^n içinde çift dolaşımı n^2; n=14 bit ~3e6. op’u ayrı sayaçtan verme — maskenin fonksiyonu.

Çözüm

function gcd(a: number, b: number): number {
  while (b) {
    const t = a % b;
    a = b;
    b = t;
  }
  return a;
}

export function maxScore(nums: number[]): number {
  const n = nums.length;
  const g: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const d = gcd(nums[i]!, nums[j]!);
      g[i]![j] = d;
      g[j]![i] = d;
    }
  }
  const N = 1 << n;
  const dp = new Array<number>(N).fill(0);
  for (let mask = 0; mask < N; mask++) {
    let bits = 0;
    for (let t = mask; t; t &= t - 1) bits++;
    if (bits % 2) continue;
    const op = (bits >> 1) + 1;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) continue;
      for (let j = i + 1; j < n; j++) {
        if (mask & (1 << j)) continue;
        const nmask = mask | (1 << i) | (1 << j);
        const cand = dp[mask]! + op * g[i]![j]!;
        if (cand > dp[nmask]!) dp[nmask] = cand;
      }
    }
  }
  return dp[N - 1]!;
}

function gcd(a: number, b: number): number {
  while (b) {
    const t = a % b;
    a = b;
    b = t;
  }
  return a;
}

export function maxScore(nums: number[]): number {
  const n = nums.length;
  const g: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const d = gcd(nums[i]!, nums[j]!);
      g[i]![j] = d;
      g[j]![i] = d;
    }
  }
  const N = 1 << n;
  const dp = new Array<number>(N).fill(0);
  for (let mask = 0; mask < N; mask++) {
    let bits = 0;
    for (let t = mask; t; t &= t - 1) bits++;
    if (bits % 2) continue;
    const op = (bits >> 1) + 1;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) continue;
      for (let j = i + 1; j < n; j++) {
        if (mask & (1 << j)) continue;
        const nmask = mask | (1 << i) | (1 << j);
        const cand = dp[mask]! + op * g[i]![j]!;
        if (cand > dp[nmask]!) dp[nmask] = cand;
      }
    }
  }
  return dp[N - 1]!;
}

Şablon bağlantısı

Atama bitmask DP: geçiş tek öğe değil çift ekler; ekstra skor çarpanı popcount’tan gelir.

Yansıma

dp[mask] maskteki sayıların en iyi skoru. Kullanılmayan iki bit bir çift. Tur popcount/2 + 1, çarpan gcd.
Aynı sayı iki çifte girmez. gcd 1 olabilir. Tur sırası çarpanı değiştirir.
Boş mask 0. Uzunluk 2n, n küçük. İki sayı: tek tur, skor gcd.