題目比較長,題意不大好理解
現在把題意抽象一下,大概是以下意思:
1.給2~20的數字中的幾個數組成數組a,其中是你可以選擇的數字;
2.選擇的規則如下:
(1).如果選擇了某個數字x,則數組a中是其倍數的數字將被劃去;
(2).假如數字n在數組a中,若n-x 的值並不在數組a中,則劃去n;
3.當沒有數字可以選取時,則此player失敗;
4.讓你找出先選的player選擇哪個數字可以勝利。若沒有選擇輸出“(所給的一句話)”
1.本題說是動態規劃,但是在我看來,這道題 沒有 狀態轉移方程,也沒有 明顯的 狀態 需要來表示。狀態轉移應該就是代碼中DP[state]是依賴於上一層的DP[state],這叫狀態轉移嗎?如果算的話應該是最直白的狀態轉移了,因為沒得選擇只有一個依賴狀態。
2.但是,我覺得這道題目確是實實在在地應用到了 記憶化搜索 的思想。因為當前狀態DP[state]的計算需要依賴的上一層狀態DP[state]在用到時是沒有得出的,是在用到時往下搜索得到的。這裡一旦搜過,就用狀態DP[state]記錄下了該狀態下做選擇的player能不能勝利(只用0和1來表示)。
3.其實在我看來,這道題目的最大亮點,應該是在上面DP[state]中所提到的這個state ~。這是一種用二進制存儲的狀態。因為數據范圍只到20,而二進制狀態存儲起碼對於31以及以下的數字還是可以存的。而且狀態表示起來簡單干淨,轉移起來干脆不拖泥帶水。通過這道題很好地學習了二進制狀態存取的方法以及位運算的知識。收益很多。
4.代碼會好好加注釋:
#include#include #include using namespace std; const int maxn = (1<<21) + 10; int n; int a[22],ans[21]; int DP[maxn],vis[maxn]; bool judge(int i,int j,int st){ return ((((1<<(a[j]-a[i]))&(~st))&&(a[j]-a[i] != 1))||(a[j]%a[i] == 0)); } int dp(int k,int state){ if(vis[state]) return DP[state]; vis[state] = 1; if(state == 0) return 0;///沒有元素可以選擇了,說明本次選擇失敗返回0; if(k == 1) return DP[state] = 1;///只有一個元素可以選擇說明成功,返回1; for(int i=0;i