網頁

2013年12月31日 星期二

UVa 11069 A Graph Problem

題意:
  1. 子集合內數字不能相鄰
  2. 要盡可能填滿,比如n=6,那麼就不能有{3,6}而是要{1,3,6},不能是{1,4}而是要{1,4,6}


想法:
  一開始很直覺的使用遞迴一直往下尋找,但是使用遞迴會TLE,換個想法,很類似高中排列組合的階梯問題,本題是一次走2階或3階:
  • n=1{1} : 1
  • n=2{1,2} : 2
  • n=3{1,2,3} : 2
  • 當n=4{1,2,3,4},有哪些情況會選到'4'? n=1({1,4})或n=2({2,4})的情況,所以n(4)=n(1)+n(2)=3
  • 當n=5{1,2,3,4,5},會選到'5'的情況有n=2({2,5})或n=3({1,3,5}),所以n(5)=n(2)+n(3)=4
  • 以此類推..