Chia Đôi Gia Tài
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một mảng gồm $N$ số nguyên dương $a_1, a_2, \dots, a_N$. Hãy kiểm tra xem có thể chia mảng thành hai tập con (không giao nhau và hợp lại bằng toàn bộ mảng) sao cho tổng các phần tử trong hai tập con bằng nhau hay không.
Cấu trúc con tối ưu (quy hoạch động 1 chiều): đặt $S = \sum a_i$. Nếu $S$ lẻ thì đáp án là NO, ngược lại dùng mảng $dp[x]$ cho biết có thể tạo tổng $x$ ($0 \le x \le S/2$) hay không.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 200$).
- Dòng thứ hai chứa $N$ số nguyên dương $a_1, \dots, a_N$ ($1 \le a_i \le 100$).
Dữ liệu ra
- In ra
YESnếu chia được, ngược lại in raNO.
Ví dụ
| Input | Output |
|---|---|
| 4\n1 5 11 5 | YES |
| 4\n1 2 3 5 | NO |
Giới hạn
- $1 \le N \le 200$
- $1 \le a_i \le 100$
Community Discussion