Tile Exchanging

Tile Exchanging [Ray Li]

Çiftçi John ahırının zeminindeki taşları yenilemek istemektedir. John ahırının alanını bilmeden N tane kare şeklinde taş almıştır. Bu taşların sırayıla bir kenarlarının uzunluğu A_1...A_N dir. Ahırının tabanının alanının M metrekare olduğunu öğrenen John zeminini kaplamak için elindeki
taşların alanının toplamını M yapmaya karar vermiştir.

Çiftçi John markete gider ve elindeki taşları değiştirmek ister market sahibi: her bir A_i büyüklüğündeki taşını B_i büyüklüğündeki taş ile değiştiririm ancak |A_i-B_i|*|A_i-B_i| kadar maliyeti olur der.

Sizden istenen N,M ve A_i dizisi veriliğinde alanı kaplamak için gereken minimum maliyeti bulmanızdır.Eğer toplamını M yapmanız imkansızsa -1 yazdırınız.

SORU KODU: tilechng

GİRDİ BİÇİMİ:

* Satır 1: Boşlukla ayrılmış iki sayı, N (1<=N<=10) and M (1<=M<=10,000).

* Satır 2..1+N: Her bir satırda A_1 den A_N'e kadar olan diziyi temsil eden N sayı yer alacaktır.
        (1<=A_i<=100).

ÖRNEK GİRDİ (file tilechng.in):

3 6
3
3
1

GİRDİ AÇIKLAMASI:

3 tane taş vardır boyutları sırasıyla 3x3, 3x3 ve 1x1 dir. Amacımız bunların toplamını M yapacak şekilde değiştirmektir.

ÇIKTI BİÇİMİ:

* Line 1: Toplamı M yapmak için gereken minimum maliyet eğer çözüm yoksa -1 yazdırınız.

ÖRNEK ÇIKTI (file tilechng.out):

5

ÇIKTI AÇIKLAMASI:

3x3 lerin bir tanesi 2x2 ile değiştirilir ve 3x3 lerin bir tanesi 1x1 ile değitririlir. Toplam mailiyet 1+4=5 olur.

--------------------------------------------------------------------------------------------------------------------------
Gönderilebilecek link:http://usaco.org/index.php?page=nov11problems
Test dataları:http://usaco.org/current/data/tilechng.zip
--------------------------------------------------------------------------------------------------------------------------


Çözüm Metni

Problem dinamik programlama ile çözülebilir. Best[i][j] sunu temsil etsin. 1 den j ye kadar olan taslari degistirerek i alani elde etmek icin minimum gerekli maliyet. Baslangic durumu olarak
best[0][0]=0 ve best[i>0][0]=sonsuz. Diger durumlar icin recursive bir cozum gelistirebiliriz.

best[i][j]=0<=k<=sqrt(i) icin min( (k-A[j])^2 + best[i-k*k][j-1] );

k j tasinin k ile degistirilmesini temsil etmektedir. Best[i][j] nin degeri A_j hangi k degeriyle degistirilirse minimum olur bunu bulup saklamaktadir. k yeni alinacak tasin bir kenar uzunlugunu belirtmektedir (k-A[j])^2 degisim maliyetini ve i-k*k 1...j-1 araligindan elde edilmesi gereken toplam alani ve best[i-k*k][j] ise bu alani 1...j-1 taslari degistirilerek elde edilmesinin minimum maliyetini saklamaktadir.

Calisma zamani hesaplamasi k*k<=i<=M ve j<=N oldugu icin 10*100*10000=10 milyon bu da demektir ki cozumumuz 1 sn de calisir.

Not: 0 boyutlu kareler olabilmektedir kod a bunu dahil etmeliyiz 100 alabilmek icin.

--------------------------------------------------------------------------------------------------------------------------

Çözüm kodu:

#include <stdio.h>

#define MAX_M 10000
#define MAX_N 10
#define INF 1000000000

int best[MAX_M+1][MAX_N+1];
int A[MAX_M+1];

int main(void)
{
  int M, N, i, j, k;

  freopen ("tilechng.in", "r", stdin);
  freopen ("tilechng.out", "w", stdout);

  scanf ("%d %d", &N, &M);
  for (i=1; i<=N; i++)
    scanf ("%d", &A[i]);

  for (i=1; i<=M; i++)
    best[i][0] = INF;

  for (j=1; j<=N; j++)
    for (i=0; i<=M; i++) {
      best[i][j] = INF;
      for (k=1; k*k<=i; k++)
      if ((A[j]-k)*(A[j]-k) + best[i-k*k][j-1] < best[i][j])
        best[i][j] = (A[j]-k)*(A[j]-k) + best[i-k*k][j-1];
    }

  if (best[M][N]==INF)
    printf ("-1\n");
  else
    printf ("%d\n", best[M][N]);

  return 0;
}