[VOJ]BWTRI
Lê Tuệ
Hình vẽ mô tả cách giải:
http://vcoder.googlegroups.com/web/bwtri.jpg?gda=TRkzaDwAAAAeop8q_4mbf8UWZgUh0AyxjiP4AgM9a09QIXpsIsHV8akMJAa0G4BtZeNvvUgKyTv9Wm-ajmzVoAFUlE7c_fAt
Bài này quy hoạch động rất nhiều chiều.
Gọi hàm F[i,s1,s2,j,k,x0,x1,x2,x3] tức là số cách thỏa mãn đến xét đến
tam giác thứ j của hàng i, tam giác này có cạnh bên phải màu k, đã
dùng (x0,x1,x2,x3) các loại tam giác của đề bài, hàng i phải thỏa mãn
có dãy tam giác phía trên trùng với dãy bit s1, dãy tam giác phía dưới
trùng với dãy bit s2.
Dễ tìm được công thức.
Tuy nhiên để nguyên như vậy ta sẽ không thể đủ bộ nhớ.
Cách giảm bộ nhớ như sau:
Do giới hạn đề bài i<=5 nên ta sẽ xét với từng i một thì bộ nhớ cần
dùng là bao nhiêu.
Xét cụ thể:
Với i=5, s1< 1<<5, s2< 1<<4, 0<=j<9, k=0 hoặc 1, số bộ số x0,x1,x2,x3
chính là số nghiệm nguyên ko âm của phương trình x0+x1+x2+x3=9,cụ thể
là 220
Với i=4, s1< 1<<4, s2< 1<<3, 0<=j<7, k=0 hoặc 1, số bộ số x0,x1,x2,x3
chính là số nghiệm nguyên ko âm của phương trình x0+x1+x2+x3=7+9, cụ
thể là 969
Với i=3, s1< 1<<3, s2< 1<<2, 0<=j<5, k=0 hoặc 1, số bộ số x0,x1,x2,x3
chính là số nghiệm nguyên ko âm của phương trình x0+x1+x2+x3=5+7+9, cụ
thể là 2024
Với i=2, s1< 1<<2, s2< 1<<1, 0<=j<3, k=0 hoặc 1, số bộ số x0,x1,x2,x3
chính là số nghiệm nguyên ko âm của phương trình x0+x1+x2+x3=3+5+7+9,
cụ thể là 2925
Với i=1, s1< 1<<1, s2< 1<<0, 0<=j<1, k=0 hoặc 1, số bộ số x0,x1,x2,x3
chính là số nghiệm nguyên ko âm của phương trình
x0+x1+x2+x3=1+3+5+7+9, cụ thể là 3276
Như vậy:
F5 có kích thước là 512*9*2*220
F4 có kích thước là 128*7*2*969
F3 có kích thước là 32*5*2*2024
F2 có kích thước là 8*3*2*2925
F1 có kích thước là 2*1*2*3276