bedzo
Joined: 18/01/2011 02:05:03
Messages: 234
Offline
|
Бидејќи има 8 предмети, а треба да има по 2 професори минимум, тогаш може да искористиме маска 2^16.
Ќе користиме 1 ако имаме вработен, 0 ако немаме. А маската ќе е 2^16 бидејќи во првиот дел на маската(до 2^ ќе проверуваме за првиот работник на предмет, а во другиот дел за вториот.
И ќе имаме динамичко со dp[N][2^16]. Каде што N e колку професори има, ама бидејќи тоа опфаќа многу голема меморија, ќе го сведиме динамичкото на dp[2][2^16]
каде што ги вртиме редовите.
|