---
author: nguyencter
tags: Panting
title: Panting Solution
---

$\Huge\text{Panting Solution}$

-------

:::info
📌 Tags: `Matching` `dp`
✍️ Writer: nguyencter
📋 Content:
[TOC]
:::

-----
## Thuật toán
## Subtask 1:
$\Large K = 1$.

Với trường hợp $k=1$ tức là $f(a,b)=min(a,b)$ thì ta có thể sử dụng cặp ghép để giải quyết bài toán này.
Ta xem mỗi hàng và mỗi cột của các ô được tô màu đen là các đỉnh để sử dụng cặp ghép.
## Subtask 2:
Trường hợp $k=2$ ta thấy chi phí để tô một hình chữ nhật lớn có thể tính được bằng cách lấy $min$ tổng chi phí của $2$ hình con tạo nên nó .

Sử dụng hàm và mảng đánh dấu để giảm độ phức tạp tính toán.

Gọi hàm $f(x,y,u,v)$ là chi phí nhỏ nhất để tô các ô trong hình chữ nhật có ô trái trên là $(x,y)$ và phải dưới là $(u,v)$.

- Duyệt hàng $i$ từ $x$ đến $u-1$ lấy $min(f(x,y,i,v)+f(i+1,y,u,v))$.
- Duyệt cột $i$ từ $y$ đến $v-1$ lấy $min(f(x,y,u,i)+f(x,i+1,u,v))$.
- Kết quả là $min$ của hàng và cột.

Kết quả là $f(1,1,n,n)$.

Độ phức tạp là $O(N^4)$.

----
Tham khảo code mẫu ở [đây](https://github.com/nguyencter/CODE/blob/main/painting.cpp).