GCA

    算滿水的題目，不過題意讀得很累 /* * GCA : "Computer is artificial subject absolutely,Math is God" */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> #include <ctime> using namespace std; #ifdef DEBUG #define VAR(a,b) decltype(b) a=(b) #define debug(...) printf( "DEBUG: " ),printf(__VA_ARGS__) #else #define VAR(a,b) decltype(b) a=(b) #define debug(...) #endif typedef unsigned int uint ; typedef long long int Int; typedef unsigned long long int UInt; #define Set(a,s) memset(a,s, sizeof (a)) #define Pln() printf( "\n" ) #define For(i,x) for ( int i=0;i<x;i++) #define CON(x,y) x##y #define M 50005 #define PB push_back #define oo (1<<29) #define FOR(a,b) for (VAR(a,(b).begin());a!=(b).end();++a)...

  DP dp[i] i表示厚度，而dp[i]的值是這個厚度當中 寬度最大的為多少 之後再用總數去扣掉即可   貌似有greedy解法，分成厚度1跟2 具體內容要參考其他blog /* * GCA : Where is the Dp,there is the wall */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> #include <ctime> using namespace std; #ifdef DEBUG #define VAR(a,b) decltype(b) a=(b) #define debug(...) printf( "DEBUG: " ),printf(__VA_ARGS__) #else #define VAR(a,b) __typeof(b) a=(b) #define debug(...) #endif typedef long long int Int; #define Set(a,s) memset(a,s, sizeof (a)) #define Pln() printf( "\n" ) #define M 104 #define PB push_back #define oo (1<<29) #define FOR(a,b) for (VAR(a,(b).begin());a!=(b).end();++a) #define eps 1e-9 inline bool xdy( double x, double y){ return x>y+eps;} inline bool xddy...

只可意會不可言傳的DP ... 附上官方題解 Tutorial D. Dima and Hares Let's look at the first hare: we chose them befoe second, or after. If it is chosen after the second, than the solution from the 2nd hare to the last doesn't depend on the first one, otherwise, we will receive the same but before the second hair will be obviously the feed hair. So, we have two dinamics: 1). d 0 i — answer for suffix as a separate task. 2). d 1 i — answer for suffix if the previous hair for this suffix is feed already. Movements: d 0 n   =   an d 1 n   =   bn d 0 i   =   max ( ai   +   d 1 i   +  1,   bi   +   d 0 i   +  1) d 1 i   =   max ( bi   +   d 1 i   +  1,   ci   +   d 0 i   +  1)   // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A::::...

難題....DP 參考了turiol跟解題報告 這題給了n,l,k 那麼我們就用這三個來做DP狀態轉移 dp[i][j][m] win j of the first i days and get total bag Probability 所以 如果拿到包包的話 dp[i+1][j+1][m+w[i]]=dp[i][j][m]*p[i] 拿到獎杯 dp[i+1][j+1][m-1]=dp[i][j][m]*p[i] 都沒拿到 dp[i+1][j][m]=dp[i][j][m]*(1-p[i]) 所以算完之後只要在n天拿到l以上的天數，並且包包不是空的的機率都可以加起來 因為代表你都拿的回去，反正拿的回去的機率全部加起來就對了啦~~~~~   // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A...

求出最長子序列，且不包含一個子字串 DP難題，要在LCS上面多開一維的空間 用來記錄病毒字串的生長，所以需要用KMP 首次深入學習了 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:...

比較簡單的DP題，為了少掉浮點數，把DP全部*10 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A A::::...

誰能告訴我DP到底是誰想出來的 真的有夠噁爛 dp(i, j) = min{dp(i-1, j), dp(i-1, j-1)+w[i]} 記得有條件 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::...

直接全暴力搜索+記憶化表單 數據感覺好像很小，過得很快 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A A:...

這題非常的複雜+麻煩，需要用到BFS+Hamilton Path+DP // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A ...

利用LIS特性去做就可以了 只是只要更新目前的就可以了 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A A:...

把滿足條件的由上到下所有組合最佳化一次   也就是DP EX index year month 0 0 1 1 0 3 2 1 2 3 1 11 4 1 12 5 2 5 6 2 8 7 3 4 dp[0]=1 dp[1]=dp[0]+1 dp[2]=dp[1]+1  (dp[0]+1) <--不滿足條件 dp[3]=dp[2]+1  (dp[1]+1 dp[0]+1)<--不滿足條件 … dp[i]=min(dp[i],dp[j]+1) j from i-1 to 0 也就是說DP是把上面最少且符合條件的配對往下給 但是+號必須絕對保留 所以一碰到+號立即break 那麼+號之後的排列組合必定都有加號 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::...