IOI 2001 Twofive

其實2個query最終也是要知道:

"Given current table, return the number of ways to fill the rest of the table"


單純的 recursion 會超時

如果是由 'A' 到 'Z' 看看有哪些未用, 然後填落去的話
由於是由小至大地填, 所以一定不會出現唔 valid 的情況



假設原本的 table是

A B C D E

F G H * *

I J * * *

K * * * *
L * * * *

例如某些方法填了 M 和 N,

A B C D E

F G H M *

I J N * *

K * * * *
L * * * *

A B C D E

F G H N *

I J M * *

K * * * *
L * * * *

這兩個方法之後再砌的方法的數目是相同的
重點是「形狀」!

可以用狀態 dp 去避免重複運算

dp 的狀態是每一row填了多少格 (不會中空, 一定是由左開始填)
每次加一個新的字母一定是加在某一row的後面

其實思路不是太複雜

不過這個構做法並不容易想出來
我是看著 sample code 來揼的..