程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1143 number game

poj 1143 number game

編輯:C++入門知識

poj 1143 number game


題目比較長,題意不大好理解

現在把題意抽象一下,大概是以下意思:

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved