Soal yang akan dibahas kali ini adalah UVa 12589 - Learning Vector. Singkatnya, kita berikan N vektor. Pilih K vektor sedemikian sehingga bila vektor-vektor itu digambar dalam poligon dengan urutan tertentu, akan menghasilkan luas daerah di atas sumbu-x terbesar.
Observasi 1:
Misalkan kita memiliki sejumlah vektor. Menggambarkannya dalam bentuk poligon dengan urutan apapun akan berakhir di suatu titik yang sama. Alasannya karena penjumlahan vektor bersifat komutatif. Permasalahan berikutnya adalah bagaimana kita menentukan urutan penggambarannya sehingga luas yang dihasilkan maksimal.
Observasi 2:
Untuk menghasilkan luas di atas sumbu-x maksimal, sejumlah vektor itu harus kita urutkan mulai dari yang "gradien"-nya terbesar. Jadi muncul strategi greedy untuk mengurutkan vektor-vektor tersebut.
Observasi 3:
Setelah terurut, kita perlu memilih vektor-vektor itu untuk menghasilkan luas maksimal. Persoalan ini dapat diselesaikan dengan DP \(O(N^4)\). Yang menjadi state adalah sekarang sedang mengevaluasi vektor ke berapa, sudah berapa vektor yang kita pilih, dan posisi koordinat y saat ini. Dengan ketiga state ini, kita tentukan apakah vektor yang sedang dievaluasi mau digunakan atau tidak. Bila digunakan, luasnya ditambah sebesar luas trapesium baru yang dibuat. Misalkan f(x,d,h) menyatakan luas maksimal saat vektor x dievaluasi, sudah mengambil d vektor, dan ketinggian (koordinat y) saat ini h.
\(\displaystyle f(x,d,h) = \left\{
\begin{array}{ll}
0 & ,(x = N) \wedge (d = K) \\
f(x+1,d,h) & ,(x < N) \wedge (d = K) \\ \max{\left( \begin{array}{l} f(x+1,d,h), \\ f(x+1,d+1,h + v[x].y) + area(h,v[x]) \end{array} \right) }& ,(x < N) \wedge (d < K) \end{array} \right. \) \(\displaystyle area(h,v) = h (h + v.y) (v.x) \) Dengan DP tersebut, kita membutuhkan memori maksimal \(O(N^4)\). Karena terlalu besar dan time limit soal ini cukup ketat, kita dapat menggunakan teknik bottom up DP dengan flying table. Sehingga memori yang dibutuhkan hanya \(O(N^3)\).
Observasi 1:
Misalkan kita memiliki sejumlah vektor. Menggambarkannya dalam bentuk poligon dengan urutan apapun akan berakhir di suatu titik yang sama. Alasannya karena penjumlahan vektor bersifat komutatif. Permasalahan berikutnya adalah bagaimana kita menentukan urutan penggambarannya sehingga luas yang dihasilkan maksimal.
Observasi 2:
Untuk menghasilkan luas di atas sumbu-x maksimal, sejumlah vektor itu harus kita urutkan mulai dari yang "gradien"-nya terbesar. Jadi muncul strategi greedy untuk mengurutkan vektor-vektor tersebut.
Observasi 3:
Setelah terurut, kita perlu memilih vektor-vektor itu untuk menghasilkan luas maksimal. Persoalan ini dapat diselesaikan dengan DP \(O(N^4)\). Yang menjadi state adalah sekarang sedang mengevaluasi vektor ke berapa, sudah berapa vektor yang kita pilih, dan posisi koordinat y saat ini. Dengan ketiga state ini, kita tentukan apakah vektor yang sedang dievaluasi mau digunakan atau tidak. Bila digunakan, luasnya ditambah sebesar luas trapesium baru yang dibuat. Misalkan f(x,d,h) menyatakan luas maksimal saat vektor x dievaluasi, sudah mengambil d vektor, dan ketinggian (koordinat y) saat ini h.
\(\displaystyle f(x,d,h) = \left\{
\begin{array}{ll}
0 & ,(x = N) \wedge (d = K) \\
f(x+1,d,h) & ,(x < N) \wedge (d = K) \\ \max{\left( \begin{array}{l} f(x+1,d,h), \\ f(x+1,d+1,h + v[x].y) + area(h,v[x]) \end{array} \right) }& ,(x < N) \wedge (d < K) \end{array} \right. \) \(\displaystyle area(h,v) = h (h + v.y) (v.x) \) Dengan DP tersebut, kita membutuhkan memori maksimal \(O(N^4)\). Karena terlalu besar dan time limit soal ini cukup ketat, kita dapat menggunakan teknik bottom up DP dengan flying table. Sehingga memori yang dibutuhkan hanya \(O(N^3)\).
Tidak ada komentar :
Posting Komentar