題意:在n*m(1<=n,m<=12)的矩陣上種植玉米,任意共邊的方格不能同時種,並且有些特定方格也不能種。問能有多少種種植的方案;
解法;很經典的狀壓模型。先將每一行的合法狀態求出來,12的時候最多377個合法狀態。然後進行與行之間的狀態轉移。最壞復雜度12*(377^2)
代碼:
/**************************************************** * author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include#include #include #include #include #include #include #include #include