Codeforces #90

d1 & d2 一齊打既比賽。
最後因為條B official soln 出錯變成unrated...如果rated應該會升的..

只做了A,B,C

不過條B 如大部分人一樣都係比佢陰左..題目本身出得很好, 個trick好反直感。

A:
頹, simulation

B:
其實題目就係要你搵min / max of avg of given既cards, 同埋剩番落黎足夠theorems可以組成一張card (視乎min定max, 總之sort左佢一路pick就係). 陰位係: 由於題目講明卡可以重複出現, 但一題題目只會出現係一張卡上面, total係有k 張卡的, 姐係話如果你已經知道哂所有 k 張卡, 而剩番既theorems仲可以組多一張卡, 咁答案都仍然係given 個k 張卡入面搵...
唉

C:
DP...雖然人地話好standard, 但我覺得唔算太容易..所以比賽入面過到真係幾開心。
思考過程有兩個observation, 第一, sort by complexity 先再做dp, 不過做dp時仍然要check到transition時唔可以由一樣complexity既update (因為要strictly increasing)  ; 第二,  我諗好明顯, bi - ai <=100   而ai 同 bi <=10^16!!  記得ZQ講過呢d好明顯就要諗下點利用。 不過先將呢個問題放係一邊, 直接諗下state 同transition先~

state:  dp( X, i , n ) :=  max total # of homework from 0 to i lessons,  pick up n lessons, and the i-th lesson have X+a[i] homework

transition:
dp(X, i, n) =
max ( dp (X+a[i] - k - a[j],  j , n -1),    if( (X+a[i])%k==0) { dp((X+a[i])/k - a[j], j, n-1} )
for all j < i

奇妙就係度..因為bi - ai <=100 , 所以我用offset X ,  0<=X<=100 黎代表第 i 個lesson既homework 數都係得既! 咁樣table size就係 100 * 50 * 50 , 非常合理既數字, 亦都大大提升左我對呢個做法既信心

當然仲有好多野要handle.. X +a[i] <= b[i] 啦.. complexity 要strictly increasing 啦..
call答案時 試哂所有X 同 i (因為可以係簡頭個d 已唔簡後面個d, 如果直接將 i 變做m 會錯)
tX = X in argmax (dp (X , i, n) )
tI = i in argmax( dp(X , i, n) )

最後recursion trace條path出黎就ko~

ps: 記錄條path 都幾麻煩...由於無咩時間加唔識, 夾硬用pair < int, pair<int, int> > naive記住parent (o:以後可以試下用map<node , id> ... by gary

PKU 2411, PKU 3797

糾結, 唔係尋晚TRAINING都唔知DP真係 一D都唔X識 (O:
PKU3797 EXACTLY係 GYN 個題
PKU 2411 係general 版 (for small h, w)

ps: 呢個問題有combinatorics既formula,  類似summation of sqrt( f(h,w) ); where f(h,w) 係 有cos function
==> for large h,w 就要用呢條野了..放入武器吧 =.=?
詳情google下d 解題報告就會見到

back to the question,
問題:  given 一個 h * w 既grid, 有幾多種方法可以用 2*1 domino 鋪滿

想, 加睇人code, 學識左一個極簡單code法, code落仲有d微少野學到

思路:
dp 四大元素: state define, transition, base case, 答案既state

state: dp( i , mask) := 直到第 i 行的masking 為 mask, 共有幾多種排法
base case: 第 0 行 所有可行既mask  x, 設dp(0, x) 為1
答案 : dp( h, (1<<w) - 1)
transition:  重點要理解既部分..為左自己記憶深刻, 詳細說明之

首先設 bit 1 代表該格已經放左野, 0 就係無, 注意此處未有咩打橫打直既考慮
假設依家我想做緊 第 i 行, 已知第 i - 1 行既state, 例如  1001
顯然 第2 , 3 個bit 一定要放一個打直既domino 黎填上面既空位
so  可行既state 一定係咁既樣:  x11x  where x 係未知數, 注意呢度既1 係代表打直既domino
so   點樣先知x 係咩呢?
其實輕鬆 recursion, 0同1都試下就ok, 不過 係呢一步放既一定要打橫既domino, 即一定要連住兩個1
當然,  x 可以係一個打直既domino as well (霸左 第 (i, j) 同 下一行既(i+1, j) )
但係唔使理佢, 只要留佢係0, 做第 i+1行時自然會補番個 1 做到相同既configuration
so transition係: dp( i, mask ) = sum of  dp(i-1, possible mask such that row i can be mask)

講咁多, 其實因為好吊詭地, 打直同打橫唔係太重要, 又或者應該話...
打直同打橫唔係直接可以表示到出黎, 所以較難明..
同一個bitmask : 例如  "1111"  配合唔同既 上一行 (只關上一行事) 可以係完全唔同既configuration: 

以一個2*2的版面說明, 假設第一行是一個橫放的domino, 那第一行的mask 就是"11"

那麼第2行也只可以放個打橫的吧, 而第2行的狀態亦為"11",  所以 dp(2, "11") 現在是 1

來看第二種排法: 我們想要2個打直的domino.
而第一行的狀態是"00" (不是"11" ! 我們希望透過"00", 讓下一行發現有空格從而補上一個 "1" , 代表打直來填補)

最後在紀錄第二行時, 正如上面所講, 我地被迫要放兩個"1" , 以填補正上方既空格















所以, 第二行的狀態都是 "11", 但代表不同的排法。
但所表示 "排滿第二行" 的狀態還是叫 dp( 2, "11" )
最後dp(2,"11") 就是 2

簡易版code:
注1:  ~a 係 bit negate, 不過會連埋sign bit , so ~a & ((1<<a)-1) 先做到想要既效果
注2: 1<<a+1  = 1<<(a+1)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;

LL dp[20][1<<12];
int h,w;
// given a state , update all state wif horizontal block
void d(int st, int i, int pos, LL from){
        if(pos >= w){dp[i][st] += (i==0? 1: from ); return;}
        d(st,i,pos+1, from);
        if(pos+1<w && !(st & (1<<pos)) && !(st&(1<<pos+1)))
                d(st | (1<<pos) | (1<<pos+1), i, pos+2, from);

}

int main(){
        while(scanf("%d%d", &h,&w), h||w){
                memset(dp,0,sizeof(dp));
                d(0,0,0,0);
                for(int i=1; i<h;i++){
                        for(int j=0; j < (1<<w);j++){
                                if(!dp[i-1][j]) continue;
                                d(~j & ((1<<w)-1), i, 0, dp[i-1][j]);
                        }
                }
                printf("%lld\n", dp[h-1][(1<<w)-1]);
        }
        return 0;
}