國大里電研社

現在大家能使用http://dcirc.twbbs.org進入本討論區

國大里電研社

登入


版面鎖定 這個主題已被鎖定,您不能編輯或回覆這個主題。
 第 1 頁 (共 1 頁)  [ 2 篇文章 ] 

2012年 3月 5日, 14:44

離線
站務管理員
站務管理員
頭像
註冊時間: 2011年 6月 4日, 05:58
文章: 58
屆數:

第二題:奇數分解
奇數分解試圖把某個正整數 N 分成比某個正整數 M 以下的相異正奇數和。舉例來說,6=5+1可以被5以下的奇數分解,而3就沒辦法被1以下的奇數分解。
給定任意的正整數N及正整數M,請算算 N 可否被M以下的奇數分解?
輸入說明
輸入檔的第一行有一個正整數K,代表接下來有K組測試資料。
以下的K行,每行各有一個正整數N (1≤N≤109)及一個正整數M (1≤M≤N)。
輸出說明
對於每一組測試資料,如果N可以被M以下的奇數分解,輸出YES;否則輸出NO。

範例一
輸入
1
6 5
輸出
YES
範例二
輸入
2
2 1
9 5
輸出
NO
YES

_________________
圖檔


回頂端 回頂端
  個人資料
 

#

2012年 3月 8日, 15:46

離線
站務管理員
站務管理員
頭像
註冊時間: 2011年 6月 4日, 05:58
文章: 58
屆數:

關於這題的解題技巧,我們利用之前說過的0/1背包問題的方式來解
因為這題只要小於M的整數都有可能被選到,所以如果使用暴力解法
那麼時間複雜度就會為O(2n)
所以只要數字過大,所花的時間會成指數成長

那麼為什麼用0/1背包問題呢?
因為在這裡選擇的是相異正整數,然後有最大權重限制(最大為N)
也就是說,奇數只能選一次,權重就是奇數的值
這不就很類似0/1背包嗎?
然後設定權重跟價值是一樣的,換句話說背包的負重會等於背包的價值
只要背包全部裝滿(也就是負重等於價值)就得解

物件我們設定0~(M + 1) / 2 - 1個,權重0~(M + 1) / 2 - 1
初始值全部設成0,DP[0][i]設定為1(可以免除超出陣列的判斷)
剩下的就以背包來解,只要在最後面判斷背包是否裝滿即可


cpp 代碼: 選擇全部
  1. #include <iostream>
  2. #include <cstdlib>
  3.  
  4. using namespace std;
  5.  
  6. int main(){
  7.     int M = 0, N = 0;
  8.     cin >> N >> M;
  9.     int len = (M + 1) / 2;
  10.     int DP[len][N + 1];
  11.  
  12.     //clear & set
  13.     for(int i = 0; i < len; i++)
  14.         for(int j = 0; j <= N; j++)
  15.             DP[i][j] = 0;
  16.     for(int i = 1; i <= N; i++)
  17.         DP[0][i] = 1;
  18.    
  19.     //start DP
  20.     for(int i = 1; i < len; i++){
  21.         for(int j = 0; j <= N; j++){
  22.             DP[i][j] = DP[i - 1][j];
  23.             if(j - (2 * i + 1) >= 0 && DP[i][j] < DP[i - 1][j - (2 * i + 1)] + 2 * i + 1)
  24.                 DP[i][j] = DP[i - 1][j - (2 * i + 1)] + 2 * i + 1;
  25.         }
  26.    
  27.     }
  28.    
  29.     if(DP[len - 1][N] == N)
  30.         cout << "Yes" << endl;
  31.     else
  32.         cout << "No" << endl;    
  33.     return 0;
  34. }

_________________
圖檔


回頂端 回頂端
  個人資料
 
顯示文章 :  排序  
版面鎖定 這個主題已被鎖定,您不能編輯或回覆這個主題。
 第 1 頁 (共 1 頁)  [ 2 篇文章 ] 

所有顯示的時間為 UTC + 8 小時


誰在線上

正在瀏覽這個版面的使用者:沒有註冊會員 和 1 位訪客


不能 在這個版面發表主題
不能 在這個版面回覆主題
不能 在這個版面編輯您的文章
不能 在這個版面刪除您的文章


搜尋:
前往 :  
cron