1. 資源問題1
-----機器分配問題
f[i,j]:=max(f[i-1,k]+w[i,j-k]);
2. 資源問題2
------01揹包問題
f[i,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]);
3. 線性動態規劃1
-----樸素最長非降子串行
f[i]:=max
4. 剖分問題1
-----石子合併
f[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);
5. 剖分問題2
-----多邊形剖分
f[i,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]);
6. 剖分問題3
------乘積最大
f[i,j]:=max(f[k,j-1]*mult[k,i]);
7. 資源問題3
-----系統可靠性(完全揹包)
f[i,j]:=max;
8. 貪心的動態規劃1
-----快餐問題
f[i,j,k]:=max;
9. 貪心的動態規劃2
-----過河 f[i]=min (not stone[i])
f(i-k)}+1} (stone[i]); +貪心壓縮狀態
10. 剖分問題4
-----多邊形-討論的動態規劃
f[i,j]:=max g為min
11. 樹型動態規劃1
-----加分二叉樹 (從兩側到根結點模型)
f[i,j]:=max;
12. 樹型動態規劃2
-----選課 (多叉樹轉二叉樹,自頂向下模型)
f[i,j]表示以i為根節點擊j門功課得到的最大學分
f[i,j]:=max;
13. 計數問題1
-----砝碼稱重
f[f[0]+1]=f[j]+k*w[j];
(1<=i<=n; 1<=j<=f[0]; 1<=k<=a[i];)
14. 遞推天地1
------核電站問題
f[-1]:=1; f[0]:=1
f[i]:=2*f[i-1]-f[i-1-m
15. 遞推天地2
------數的劃分
f[i,j]:=f[i-j,j]+f[i-1,j-1];
16. 最大子矩陣1
-----一最大01子矩陣
f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1;
ans:=maxvalue(f
17. 判定性問題1
-----能否被4整除
g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false;
g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j)
18. 判定性問題2
-----能否被k整除
f[i,j±n[i] mod k]:=f[i-1,j]; -k<=j<=k; 1<=i<=n
20. 線型動態規劃2
-----方塊消除遊戲
f[i,i-1,0]:=0
f[i,j,k]:=max;
ans:=f[1,m,0];
21. 線型動態規劃3
-----最長公共子串，lcs問題
f[i,j]=0 (i=0)&(j=0);
f[i-1,j-1]+1 (i>0,j>0,x[i]=y[j]);
max} (i>0,j>0,x[i]<>y[j]);
22. 最大子矩陣2
-----最大帶權01子矩陣o(n^2*m)
枚舉行的起始，壓縮進數列，求最大欄位和，遇0則清零
23. 資源問題4
-----裝箱問題(判定性01揹包)
f[j]:=(f[j] or f[j-v[i]]);
24. 數字三角形1
-----樸素の數字三角形
f[i,j]:=max(f[i+1,j]+a[i,j],f[i+1,j+1]+a[i,j]);
25. 數字三角形2
-----晴天小豬歷險記之hill
同一階段上暴力動態規劃
f[i,j]:=min(f[i,j-1],f[i,j+1],f[i-1,j],f[i-1,j-1])+a[i,j];
26. 雙向動態規劃1
數字三角形3
-----小胖**
f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j]);
27. 數字三角形4
-----過河卒
//邊界初始化
f[i,j]:=f[i-1,j]+f[i,j-1];
28. 數字三角形5
-----樸素的打磚塊
f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]);
29. 數字三角形6
-----優化的打磚塊
f[i,j,k]:=max;
30. 線性動態規劃3
-----打鼴鼠』
f[i]:=f[j]+1;(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]);
31. 樹形動態規劃3
-----貪吃的九頭龍
f[i,j,k]:=min(f[x1,j1,1]+f[x2,j-j1-1,k]+d[k,1]*cost[i,fa[i]]] , f[x1,j1,0]+f[x2,j-j1,k]+d[k,0]*cost[i,fa[i]] );
f[0,0,k]:=0; f[0,j,k]:=max(j>0)
d[i,j]:=1 if (i=1) and (j=1)
1 if (i=0) and (j=0) and (m=2)
0 else
32. 狀態壓縮動態規劃1
-----炮兵陣地
max(f[q*(r+1)+k],g[j]+num[k]);
if (map[i] and plan[k]=0) and
((plan[p] or plan[q]) and plan[k]=0);
33. 遞推天地3
-----情書抄寫員
f[i]:=f[i-1]+k*f[i-2];
34. 遞推天地4
-----錯位排列
f[i]:=(i-1)(f[i-2]+f[i-1]);
f[n]:=n*f[n-1]+(-1)^(n-2);
35. 遞推天地5
-----直線分平面最大區域數
f[n]:=f[n-1]+n
:=n*(n+1) div 2 + 1;
36. 遞推天地6
-----折線分平面最大區域數
f[n]:=(n-1)(2*n-1)+2*n;
37. 遞推天地7
-----封閉曲線分平面最大區域數
f[n]:=f[n-1]+2*(n-1);
:=sqr(n)-n+2;
38 遞推天地8
-----凸多邊形分三角形方法數
f[n]:=c(2*n-2,n-1) div n;
對於k邊形
f[k]:=c(2*k-4,k-2) div (k-1); //(k>=3)
39 遞推天地9
-----catalan數列一般形式
1,1,2,5,14,42,132
f[n]:=c(2k,k) div (k+1);
40 遞推天地10
-----彩燈布置
排列組合中的環形染色問題
f[n]:=f[n-1]*(m-2)+f[n-2]*(m-1); (f[1]:=m; f[2]:=m(m-1);
41 線性動態規劃4
-----找數
線性掃瞄
sum:=f[i]+g[j];
(if sum=aim then getout; if sum
42 線性動態規劃5
-----**的翅膀
min:=min;
if w[i]/w[j]
43 剖分問題5
-----最大獎勵
f[i]:=max(f[i],f[j]+(sum[j]-sum[i])*i-t;
44 最短路1
-----floyd
f[i,j]:=max(f[i,j],f[i,k]+f[k,j]);
ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j];
45 剖分問題6
-----小h的小屋
f[l,m,n]:=f[l-x,m-1,n-k]+s(x,k);
46 計數問題2
-----隕石的秘密（排列組合中的計數問題）
ans[l1,l2,l3,d]:=f[l1+1,l2,l3,d+1]-f[l1+1,l2,l3,d];
f[l1,l2,l3,d]:=sigma(f[o,p,q,d-1]*f[l1-o,l2-p,l3-q,d]);
47 線性動態規劃
------合唱隊形
兩次f[i]:=max＋列舉**結點
48 資源問題
------明明的預算方案：加花的動態規劃
f[i,j]:=max(f[i,j],f[l,j-v[i]-v[fb[i]]-v[fa[i]]]+v[i]*p[i]+v[fb[i]]*p[fb[i]]+v[fa[i]]*p[fa[i]]);
49 資源問題
-----化工場裝箱員
50 樹形動態規劃
-----聚會的快樂
f[i,2]:=max(f[i,0],f[i,1]);
f[i,1]:=sigma(f[t[i]^.son,0]);
f[i,0]:=sigma(f[t[i]^.son,3]);
51 樹形動態規劃
-----皇宮看守
f[i,2]:=max(f[i,0],f[i,1]);
f[i,1]:=sigma(f[t[i]^.son,0]);
插頭DP小結
因為獨立插頭還有最小表示法沒有打過，獨立插頭沒看懂，廣義路徑連看都沒看過，所以這些不再本文的總結範圍內。去年學插頭dp的時候還是很懼怕的，也只做了一題，還是按著課件對著標程打的。還好今年終於懂得原理了。其實打多了也變成模板了 當然每題的轉移不一樣 插頭dp有下面的分類 按模型 多迴路問題 單迴路問題...
DP接頭終端電阻介紹
終端電阻和偏置電阻 乙個正規的rs 485網路 比如mpi，dp 應使用終端電阻和偏置電阻。在網路連線線非常短 臨時或實驗室測試時也可以不使用終端和偏置電阻。終端電阻 型網路兩端 相距最遠的兩個通訊埠上 併聯在一對通訊線上的電阻。根據傳輸線理論，終端電阻可以吸收網路上的反射波，有效地增強訊號強度。兩...
關於dp的斜率優化
廢話在後面講 以下引用自2006冬令營湯澤 斜率優化，亦就是說把決策與決策之間表示成乙個類似斜率的式子，進一步分析其中的單調性，並用佇列維護其有用決策。因此斜率優化又稱為佇列優化。我們來看下 中講的鋸木場選址 ceoi2004 題目描述 從山頂上到山底下沿著一條直線種植了n棵老樹。當地的 決定把他們...