Çəmənlik üçün Hasar#1526

Çəmənlik üçün Hasar (Həll təhlili)

Üçbucağın tərəfləri $a, b, c$ a, b, c olan sahəsi area funksiyasında Heron düsturu ilə hesablanır:

S = (p (p - a) (p - b) (p - c)), b u r a d a p = (a + b + c) /2

S = \sqrt{(p (p - a)(p - b)(p - c))},~burada~p = (a + b + c) / 2

Tutaq ki, $P$ mövcud çəpər parçalarının bəzi alt yığınıdır. FindSol( $ma s k$ ) funksiyası bu alt yığının parçalarından düzəldilmiş üçbucaqlarla əhatə edilə bilən maksimum sahəni tapır.

Dəyişən $ma s k$ alt yığının maskasını təmsil edir: bu, $16$ bitlik ədəd olub, $i$ -ci biti $1$ -ə bərabərdir, əgər alt yığın $P$ $f e n ces [i]$ fences[i] parçasını ehtiva edirsə, və əks halda $0$ -a bərabərdir.

Problemin cavabı $f e n ces$ massivindəki ədədlərin sayı $n$ olmaqla FindSol( $2^{n} - 1)$ 2^n - 1) qiyməti olacaq.

Bütün mümkün maskalar üçün $ma s k$ qiymətləri $0$ -dan $2^{16} - 1$ 2^{16} - 1 -ə qədər olan aralıqda yatır (çünki şərtə görə, ən çoxu $16$ çəpər parçası mövcuddur). $b es t [ma s k]$ best[mask] hüceyrəsində $ma s k$ maskasına uyğun gələn çəpər parçalarının alt yığını ilə əhatə edilə bilən maksimum sahə saxlanılır.

FindSol( $ma s k$ ) hesablamaq üçün $i, j, k$ i, j, k çəpər parçalarının bütün mümkün üçlükləri nəzərdən keçirilməlidir ki, onlar $ma s k$ içində yer alırlar. Hər üçlük üçün üçbucaq bərabərsizliyi yoxlanılır ki, bu parçalarla üçbucaq düzəltmək mümkün olsun. Əgər üçbucaq mümkündürsə, bu zaman cəmi hesablanır:

a r e a (f e n ces [i], f e n ces [j], f e n ces [k]) + F in d S o l (ma s k i, j, k)

area(fences[i], fences[j], fences[k]) + FindSol(mask \ {i, j, k})

Sonra bu üçlüklər $(i, j, k)$ (i, j, k) nəzərdən keçirilir və cəmin ən böyük olduğu üçlük seçilir. Bu maksimum dəyər $b es t [ma s k]$ best[mask] hüceyrəsinə mənimsədilir:

F in d S o l (ma s k) = (i, j, k) \in ma s k 0 \leq i < j < k < n max (a r e a (f e n ces [i], f e n ces [j], f e n ces [k]) + F in d S o l (ma s k ∖ {i, j, k}))

FindSol(mask) = \max_{\substack{(i,j,k) \in mask \\ 0 \le i < j < k < n}} (area(fences[i], fences[j],fences[k]) + FindSol(mask \setminus \{i, j, k\}))

Əgər əvvəlcə çəpər parçalarının uzunluqlarını sıraya düzsək (sıralasaq), bu durumda üçbucaq bərabərsizliyini yoxlayanda (təqdim olunan parçaların tərəfləri $f e n ces [i], f e n ces [j], f e n ces [k]$ fences[i], fences[j], fences[k]-dir), yalnız bir şərti yoxlamaq kifayətdir:

f e n ces [i] + f e n ces [j] > f e n ces [k]

fences[i] + fences[j] > fences[k]

Çünki sıralamanın nəticəsi olaraq bu təqdimlər təmin edilir:

f e n ces [i] \leq f e n ces [j] \leq f e n ces [k],

fences[i] \le fences[j] \le fences[k],

buradan həmişə belə çıxır ki,

f e n ces [i] + f e n ces [k] > f e n ces [j] v ə f e n ces [j] + f e n ces [k] > f e n ces [i] .

fences[i] + fences[k] > fences[j] və fences[j] + fences[k] > fences[i].

Misal

Birinci testdə optimal olaraq $(4, 5, 6)$ (4, 5, 6) və $(7, 8, 9)$ (7, 8, 9) tərəfli üçbucaqları qurmaqdır. Bu vəziyyətdə cəmi əhatə olunan sahə $36.7544$ -ə bərabərdir.

İkinci testdə cavab $0$ -ə bərabərdir, çünki çəpər parçalarından heç bir üçbucaq düzəltmək mümkün deyil.

Üçüncü testdə $(4, 4, 4)$ (4, 4, 4) tərəfli bir üçbucaq düzəldilməlidir. Diqqət edin ki, çəpər uzunluqları təkrarlana bilər.

Alqoritmin realizasiyası

Globall dəyişənlər elan edəcəyik.

#define MAX 16
double best[1<<MAX];
int f[MAX+1];

area funksiyası üçbucağın sahəsini Heron düsturu ilə hesablamağın üsülunu təqdim edir.

double area(int a, int b, int c)
{
  double p = (a + b + c) / 2.0;
  return sqrt(p * (p - a) * (p - b) * (p - c));
}

FindSol funksiyası maska $ma s k$ -da daxil edilən çəpərlərdən düzəldilmiş üçbucaqlarla əhatə edilə bilən maksimum sahəni qaytarır.

double FindSol(int mask)
{

Əgər $b es t [ma s k]$ best[mask] massivindəki dəyər sıfırdan böyük və ya sıfıra bərabərdirsə, bu dəyər artıq hesablanmışdır və funksion həmin dəyəri qaydar. Bu, təkrar hesablanmalardan qaçmağa və alqoritmin işini sürətləndirməyə imkan verir.

  if (best[mask] >= 0.0) return best[mask];

$b es t [ma s k] = 0$ best[mask] = 0 ilə inizializasiya edək.

  best[mask] = 0;

Maska $ma s k$ -da yer alan müvafiq çəpərləri olan $(i, j, k)$ (i, j, k) indekslərinin bütün mümkün üçlüklərini nəzərdən keçirək.

  for (int i = 0; i < n - 2; i++)     if (mask & (1 << i))
  for (int j = i + 1; j < n - 1; j++) if (mask & (1 << j))
  for (int k = j + 1; k < n; k++)     if (mask & (1 << k))

Üçbucaq mövcudluğu şərti yoxlanır. Çəpərlər əvvəlcədən sıralandığı üçün üçbucağın mövcud olduğunu təmin etmək üçün bu şərt kifayətdir.

    if (f[i] + f[j] > f[k])

Əgər üçbucaq mövcuddursa, cəmi hesablayaq:

cari üçbucağın sahəsi $a r e a (f [i], f [j], f [k])$ area(f[i], f[j], f[k]);
üstəgəl bu üçlükdə istifadə edilənləri çıxartmaqla qalan çəpərlərlə əhatə edilə bilən maksimum sahə:

F in d S o l (ma s k^(1 << i)^(1 << j)^(1 << k))

FindSol(mask~\hat{}~(1 << i)~\hat{}~(1 << j)~\hat{}~(1 << k))

      best[mask] = max(best[mask], area(f[i],f[j],f[k]) + 
          FindSol(mask ^ (1 << i) ^ (1 << j) ^ (1 << k)));
  return best[mask];
}

Proqramın əsas hissəsi. Çəpərlərin sayını $n$ oxuyuruq.

while (scanf("%d",&n) == 1)
{
  memset(f,0,sizeof(f));

Çəpərlərin uzunluqlarını oxuyuruq və onları qeyri-azalan sıra ilə sıralayırıq.

  for (i = 0; i < n; i++) scanf("%d",&f[i]);
  sort(f,f + n);

$b es t$ massivini inizializasiya edirik.

  for (i = 0; i < (1 << MAX); i++) best[i] = -1.0;

Cavabı hesablamaq və çap etmək.

  printf("%.4lf\n",FindSol((1 << n) - 1));
}