Chia Đôi Gia Tài

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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 YES nếu chia được, ngược lại in ra NO.
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$
Draft saved