Link Sub: http://www.spoj.com/PTIT/problems/BCCHIANHOM/
Người Gửi: Default
- Problem:
Cho dãy số A gồm N số (N <= 10) a1, a2, .., an. và một số nguyên dương K(1 < K < N). Hãy đưa ra số cách để chặt dãy số thành K nhóm (các phần tử trong nhóm là liên tiếp) mà các nhóm có tổng bằng nhau.Input
Dòng đâu tiên bao gồm 2 số nguyên n và k (0 < n <= 12, 0 < k <= n)
Dòng tiếp theo bao gồm n số nguyên a1, a2, …, an (-10000 <= ai <= 10000)
Output
In ra số cách thỏa mãn.
Example:
In ra số cách thỏa mãn.
Input
3 2
-2 0 -2
Output:
2
Input
3 2
1 2 3
Output:
1
- Solution:
- Sử dụng QHĐ cơ bản: lưu tổng giá trị của mảng trước đó tại mỗi phần tử (arr[i]=arr[i-1]+value)
VD: i:1-3 {-2 0 -2} -> arr[]={0 -2 -2 -4} (i:0->3)
- Đệ quy - quay lui:
+ Vì dãy chặt tạo thành các nhóm và tổng số phần tử các nhóm luôn = n -> Nên với mỗi arr[i] sẽ là trường hợp tổng giả sử có thể chặt được. và ta có vt=i;
+ Với mỗi tổng giả sử có được, ta lặp lại hành động với dãy arr[vt+1->n];
(p/s tổng có từ quy hoạch trên ta có SUM_[i->j] = arr[j]-arr[i-1]).Input
3 2
1 2 3
Output:
1