my_动态规划
步驟：
1.動(dòng)態(tài)規(guī)劃的哪種類型（1.背包（選和不選） ，2.區(qū)間dp（小區(qū)間推大區(qū)間） 3.線性dp? ， 4.樹形dp)
+普通dp? ?or? ?判定dp 哪個(gè)好實(shí)現(xiàn)（復(fù)習(xí)時(shí)若該題用判定，思考為啥不用普通）
2.狀態(tài)表示及其含義(先看數(shù)據(jù)范圍）（也可聯(lián)想最終狀態(tài)來輔助）
(2,3步驟）可以顛倒，有時(shí)推出從誰轉(zhuǎn)移可以得到狀態(tài)表示
3.當(dāng)前狀態(tài)從誰轉(zhuǎn)移而來 / 當(dāng)前狀態(tài)可以推導(dǎo)那些狀態(tài)?->轉(zhuǎn)移方程
4.處理邊界+初始化
記搜都可以轉(zhuǎn)化為dp，所以寫dp時(shí)可以先用記搜想一想，而dp不一定都能轉(zhuǎn)化為記搜
兩種寫法記搜(遞歸）dp（遞推）
dp初始化為負(fù)極大值大多是因?yàn)楸苊鉄o效轉(zhuǎn)移，參考失衡天平，，dp也有初始化為極大值的
關(guān)于狀態(tài)壓縮：如果當(dāng)前狀態(tài)從前i-1轉(zhuǎn)移而來，可以直接壓掉表示i的那一維
? ? ? ? ? ? ? ? ? ? ? ? ?如果當(dāng)前狀態(tài)只從第i-1位轉(zhuǎn)移而來，第一維要保留，但可以滾動(dòng)數(shù)組優(yōu)化
01背包模板,這個(gè)也看一下吧,選前i個(gè)的寫法，不能忘其根本***（但是做題不建議加上那一維，除非題目一定要嚴(yán)格維護(hù)第i-1種狀態(tài)，而不是前i-1種狀態(tài)）若硬要加，先看（洛谷）NASA的食物計(jì)劃
補(bǔ)充：
?01背包原本的狀態(tài)轉(zhuǎn)移方程式：
dp[i][j]=dp[i-1][j],（所以dp[i][j]本質(zhì)上是從前i-1轉(zhuǎn)移而來）
,dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+c[i])
易發(fā)現(xiàn)當(dāng)前狀態(tài)只與上一個(gè)（本質(zhì)上是前i-1個(gè)）有關(guān)，所以可以用滾動(dòng)數(shù)組優(yōu)化，用一維數(shù)組存儲(chǔ)上一個(gè)（i-1）的值
然后用i來更新上一個(gè)的值，但我們更新時(shí)當(dāng)前物品a[i]只能選一次，正序可能會(huì)導(dǎo)致物品選多次，逆序則保證前面的dp[j]存儲(chǔ)的是上個(gè)狀態(tài)最大值，最多用一次i
但是01背包精髓還是在于二維的01背包的狀態(tài)轉(zhuǎn)移方程式（對(duì)于前i個(gè)的理解）
（洛谷）采藥（01背包模板）
#include <iostream> #include <algorithm> using namespace std; #define ll long long int t,m,w[101],c[101],f[1001]; int main() {scanf("%d%d",&t,&m);for(int i=1;i<=m;i++)scanf("%d%d",&w[i],&c[i]);for(int i=1;i<=m;i++){for(int j=t;j>=w[i];j--){f[j]=max(f[j],f[j-w[i]]+c[i]);}}printf("%d",f[t]);return 0; }1.kkksc03考前臨時(shí)抱佛腳(01背包）
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <stdlib.h> using namespace std; int s[5],sub[21],f[21][1200],t1,v; long long tot; int main() {scanf("%d%d%d%d",&s[1],&s[2],&s[3],&s[4]);for(int i=1;i<=4;i++){v=0;t1=0;memset(f,0,sizeof(f));//memset(sub,0,sizeof(sub));for(int j=1;j<=s[i];j++){scanf("%d",&sub[j]);v+=sub[j];//總共需要花多少時(shí)間 }for(int j=1;j<=s[i];j++)//物品個(gè)數(shù) {for(int k=1;k<=v/2;k++)//背包容量，，使背包容量盡量==v/2，使得左右腦所耗時(shí)間基本相等 {if(k<sub[j])//模板 f[j][k]=f[j-1][k];else{f[j][k]=max(f[j-1][k-sub[j]]+sub[j],f[j-1][k]);//價(jià)值與重量相等，背包容量為時(shí)間 t1=max(t1,f[j][k]);//算出背包容量為v/2的時(shí)候最多的價(jià)值，，即最多的時(shí)間 }}}tot+=max(t1,v-t1); }cout<<tot;return 0; }2.(洛谷）5倍經(jīng)驗(yàn)日
#include <iostream> using namespace std; long long lose[2000],win[2000],use[2000]; long long f[2000]; int main() {int n,x;scanf("%d%d",&n,&x);for(int i=1;i<=n;i++){scanf("%d%d%d",&lose[i],&win[i],&use[i]);}for(int i=1;i<=n;i++){for(int j=x;j>=0;j--){long long tem=f[j];//如果所剩藥的數(shù)量夠，比較（打敗，輸?shù)?#xff0c;之前f[j]的值）的情況 if(j>=use[i]) //如果藥不夠，比較（打敗，之前f[j]的值）的情況 f[j]=max(f[j],f[j-use[i]]+win[i]);f[j]=max(f[j],tem+lose[i]); }}printf("%lld",5*f[x]);return 0; }（牛客）牛牛的旅游紀(jì)念品（基于01背包的背包dp）(理解選前i個(gè)和選第i個(gè)區(qū)別)***（求最值）
（牛客）音量調(diào)節(jié)（01背包變形+判定dp）（嚴(yán)格從第i-1種狀態(tài)轉(zhuǎn)移，不能壓維度，可用滾動(dòng)數(shù)組） （求最值）
（牛客）簡(jiǎn)單的煩惱（01背包+貪心）（求最值）
（牛客）美味菜肴（01背包+貪心：推公式）（求最值）
（牛客）codeforces（跟上一題一樣）
（洛谷）最大約數(shù)和（很隱蔽的01背包）（求最值）
（洛谷）有線電視網(wǎng)（樹形dp+分組背包+01背包）
（洛谷）集合 Subset Sums（背包求方案數(shù)）（方案數(shù)**）
（洛谷）找啊找啊找GF（三重費(fèi)用dp，一遍ac）（求最值）
（洛谷）搭配購買（01背包+并查集）（求最值）
（洛谷）yyy2015c01 的 U 盤（01背包+二分答案）（求最值）
? 完全背包（跟01差不多，只是第i件物品能選無限次）
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
（洛谷）瘋狂的采藥（完全背包模板）
?
（洛谷）四方定理（背包dp（完全背包）） （求方案數(shù)**）
（洛谷）A+B Problem（再升級(jí)）（隱蔽的完全背包思想）（求方案數(shù)*）
（洛谷）質(zhì)數(shù)和分解
（牛客）貨幣系統(tǒng)（完全背包變形+思維+判定dp）
（洛谷）投資的最大效益
（洛谷）Buying Hay S（題目理解，細(xì)節(jié)處理***）
（洛谷）紀(jì)念品（經(jīng)典題目+狀態(tài)壓縮+倒序的完全背包）
（洛谷）飛揚(yáng)的小鳥（細(xì)節(jié)題+難想的完全背包+二維完全背包寫法）（需要再看看）
（洛谷）Cut Ribbon（完全背包+要求背包剛好裝滿）
線性dp
（牛客）舔狗舔到最后一無所有
#include <iostream> #include <cstring> #include <algorithm> using namespace std; #define int long long const int N=100010,mod=1e9+7; int f[3][N];// f[0/1/2][i]前i天且第i天去第0/1/2家購買方案 // f[0][i]=(f[1][i-1]+f[2][i-1]+f[1][i-2]+f[2][i-2]) // f[1][i]=(f[0][i-1]+f[2][i-1]+f[0][i-2]+f[2][i-2]) // f[2][i]=(f[1][i-1]+f[0][i-1]+f[1][i-2]+f[0][i-2])signed main() {int T;cin>>T;f[0][0]=f[1][0]=f[2][0]=0;f[0][1]=f[1][1]=f[2][1]=1;f[0][2]=f[1][2]=f[2][2]=3;for(int i=3;i<N;i++){f[0][i]=(f[1][i-1]+f[2][i-1]+f[1][i-2]+f[2][i-2])%mod;f[1][i]=(f[0][i-1]+f[2][i-1]+f[0][i-2]+f[2][i-2])%mod;f[2][i]=(f[1][i-1]+f[0][i-1]+f[1][i-2]+f[0][i-2])%mod;}while(T--){int n;cin>>n;cout<<(f[0][n]%mod+f[1][n]%mod+f[2][n]%mod)%mod<<endl;} }我們發(fā)現(xiàn)第i天去哪一家都是一樣的，3家關(guān)系是相同的，因此可以縮小至一維，只要在初始值乘3，得到的結(jié)果也是原來的三倍#include <iostream> #include <cstring> #include <algorithm> using namespace std; #define int long long const int N=100010,mod=1e9+7; int f[N]; signed main() {int T;cin>>T;f[0]=0;f[1]=3;f[2]=9;for(int i=3;i<N;i++)f[i]=(f[i-1]*2%mod+f[i-2]*2%mod)%mod;while(T--){int n;cin>>n;cout<<f[n]<<endl;} }（牛客）烏龜棋
（牛客）失衡天平（經(jīng)典）
（牛客）購物
?（牛客）隊(duì)伍配置（經(jīng)典）
（洛谷）守望者的逃離（非傳統(tǒng)dp）
（洛谷）擺花（方案數(shù)）
（洛谷）線段（特殊的定義狀態(tài)方法）
（牛客）釘子和小球 （由當(dāng)前狀態(tài)推導(dǎo)其他狀態(tài)）
(牛客)可愛の星空（很像區(qū)間dp的dfs）?
(洛谷)尼克的任務(wù)(線性dp,由當(dāng)前狀態(tài)推導(dǎo)其他狀態(tài)，初始化為負(fù)極大值）
(牛客）打鼴鼠（特殊的定義狀態(tài)方法）
(牛客）被3整除的子序列（線性dp）
(牛客）刪括號(hào)（字符串dp不算很懂）
(洛谷)編輯距離(字符串dp，體現(xiàn)動(dòng)態(tài)規(guī)劃無后效性，很妙)
(洛谷）子串 (字符串dp+滾動(dòng)數(shù)組）（似懂非懂）
(洛谷）字串距離（字符串dp）（有點(diǎn)啟發(fā)）
(洛谷）傳球游戲（提示：循環(huán)順序即遞推順序，要嚴(yán)謹(jǐn)！！！）
(洛谷）雷濤的小貓（嚴(yán)謹(jǐn)循環(huán)順序，一遍ac）
(洛谷）最大正方形（題解的:很妙，但特殊，自己寫的:線性dp+稍微有點(diǎn)復(fù)雜的前綴和）
(洛谷）最大正方形II (跟上一題的差不多，特殊）
(牛客）禪（簡(jiǎn)單線性dp）
(洛谷）逆序?qū)?shù)列（前綴和+dp) 錯(cuò)因：對(duì)逆序?qū)Σ皇?#xff09;
(洛谷）英雄聯(lián)盟（循環(huán)順序，循環(huán)方向因遵循推導(dǎo)方向，特別是壓縮前i-1狀態(tài)時(shí)，不能忘了推導(dǎo)方向）
(牛客）斗地主（取模，需要注意的地方）
(牛客）美麗序列（精準(zhǔn)狀態(tài)定義）
(牛客）小紅的子序列（通過上一題有感而發(fā)，寫出來）
(洛谷)覆蓋墻壁(藍(lán)橋杯原題）#include <iostream> using namespace std; #define ll long long ll n,f[2000000],sum[2000000];//f[i]為填滿前2*i個(gè)方格的總方案數(shù)，sum為前綴和 int main() {cin>>n;f[0]=f[1]=1;f[2]=2,f[3]=5;sum[0]=1,sum[1]=2,sum[2]=4,sum[3]=9;//初始化 for(int i=4;i<=n;i++){f[i]=sum[i-1]+sum[i-3];f[i]%=100000;sum[i]=(sum[i-1]+f[i])%100000;}cout<<f[n]%10000;return 0;} /*考慮放在最后那一部分 1.放2*1磚塊（豎放）方案數(shù)：f[i-1] 2.放2個(gè)2*1磚塊（橫放）方案數(shù)：f[i-2]//這里不考慮豎放是因?yàn)闀?huì)重復(fù)：f[i-1]最后一個(gè)本來就是豎放然后f[i]也豎放 3.放一個(gè)L型磚塊（因?yàn)榭煞D(zhuǎn)，所以要乘2） { 1.再放一個(gè)L型磚塊（剛好互補(bǔ)）方案數(shù)：f[i]=f[i-3] 2.放一個(gè)2*1型磚塊（豎放）再放一個(gè)L型磚塊 方案數(shù)：f[i]=f[i-4] 3.2×1 的磚塊可以交替著放下去，再補(bǔ)上一個(gè) L 型磚塊，從而消去這個(gè)突出,直到 2*1 磚塊和 L 型磚塊恰好填滿墻壁(f[0]) } 所以總方案數(shù)：f[i-1]+f[i-2]+2*sum[i-3]=sum[i-1]+sum[i-3]?滾動(dòng)數(shù)組模板（牛客）音量調(diào)節(jié)
#include <iostream> #include<cstring> #include <algorithm> using namespace std; #define inf 0x3f3f3f3f int n,be,maxx; bool dp[2][2000]; int main() { // memset(dp,-inf,sizeof dp);// cout<<dp[1];cin>>n>>be>>maxx;dp[0][be]=1;for(int i=1;i<=n;i++){int x;cin>>x;bool flag=false;for(int j=0;j<=maxx;j++){if(dp[i&1^1][j])//i&1只有奇和偶兩種情況{if(j>=x)dp[i&1][j-x]=1,flag=true;if(j+x<=maxx)dp[i&1][j+x]=1,flag=true;dp[i&1^1][j]=false;//要把之前的i-1初始化回去，（如果下一次能把上上一次的覆蓋掉則沒關(guān)系）}}if(!flag){cout<<-1;return 0;}}int ans=-1;for(int j=0;j<=maxx;j++){if(dp[n&1][j])ans=j;}cout<<ans;return 0; }（雙線程）方格取數(shù)（牛客）
#include <iostream> #include <algorithm> using namespace std; int ma_p[11][11],dp[11][11][11][11]; long long ans=0; int main() {int n;cin>>n;while(1)//輸入 {getchar();int x,y,z;scanf("%d%d%d",&x,&y,&z);if(x==y&&y==z&&z==0)break;else ma_p[x][y]=z;}for(int a=1;a<=n;a++)//到點(diǎn)（a,b),(c,d)的路徑的和for(int b=1;b<=n;b++)for(int c=1;c<=n;c++)for(int d=1;d<=n;d++){if(a==c&&b==d)//若兩點(diǎn)重合{dp[a][b][c][d]=dp[a-1][b][c][d-1]+ma_p[a][b];}else{int tem=0;if(dp[a-1][b][c-1][d]>tem)tem=dp[a-1][b][c-1][d];//四種情況，因?yàn)榈侥硞€(gè)點(diǎn)的兩條路徑步數(shù)一定相等if(dp[a-1][b][c][d-1]>tem)tem=dp[a-1][b][c][d-1];//所以兩個(gè)點(diǎn)必須同時(shí)動(dòng)if(dp[a][b-1][c-1][d]>tem)tem=dp[a][b-1][c-1][d];if(dp[a][b-1][c][d-1]>tem)tem=dp[a][b-1][c][d-1];dp[a][b][c][d]=tem+ma_p[a][b]+ma_p[c][d];}}printf("%d",dp[n][n][n][n]);return 0; }（洛谷）傳紙條?
拓?fù)?#43;dp
（洛谷）旅行計(jì)劃
（洛谷）綠豆蛙的歸宿（期望dp+拓?fù)?#xff09;
最長(zhǎng)公共子序列
（洛谷）最長(zhǎng)公共子序列（直接看代碼）
樸素算法;
當(dāng)s1==s2,dp[i][j]=dp[i-1][j-1]+1
當(dāng)s1[i]!=s2[j],dp[i][j]=max(dp[i-1][j],dp[i][j-1])
樸素算法o(n^2)超時(shí)。。。 #include<iostream> using namespace std; int dp[20000][20000],arr1[200000],arr2[200000]; int main() {int n,maxn=0;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&arr1[i]);for(int i=1;i<=n;i++)scanf("%d",&arr2[i]);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(arr1[i]==arr2[j])dp[i][j]=dp[i-1][j-1]+1;else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}if(dp[i][j]>maxn)maxn=dp[i][j];}}printf("%d",maxn);return 0; }離散化，轉(zhuǎn)化為最長(zhǎng)上升子序列o(nlogn)，只能用于A串各元素互不相同的情況給它們重新標(biāo)個(gè)號(hào)：把3標(biāo)成a,把2標(biāo)成b，把1標(biāo)成c，，于是變成： A: a b c d e B: c b a d e 出現(xiàn)一個(gè)性質(zhì)，只要這個(gè)子序列在B中單調(diào)，則它就是A的子序列，所以問題轉(zhuǎn)化成求最長(zhǎng)上升子序列 #include <iostream> #include <unordered_map> #include <algorithm> using namespace std; unordered_map<int,int>mark; int n,arr2[200000],d[200000],len=1; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);mark.insert(pair<int,int>(x,i));//用一個(gè)數(shù)組記錄一下每個(gè)數(shù)字變成了什么，相當(dāng)于離散化了一下，3-1；2-2；1-3；4-4；5-5 }for(int i=1;i<=n;i++)scanf("%d",&arr2[i]);for(int i=1;i<=n;i++){arr2[i]=mark[arr2[i]];}d[len]=arr2[1];for(int i=2;i<=n;i++){if(arr2[i]>d[len])d[++len]=arr2[i];else{int x=lower_bound(d+1,d+1+len,arr2[i])-d;d[x]=arr2[i];}}printf("%d",len);return 0; }多重背包
樸素版本（將所有物品看成單獨(dú)的物品，轉(zhuǎn)化成01背包）O(n^3)
二進(jìn)制優(yōu)化版本（因?yàn)槿魏我粋€(gè)數(shù)都可以由二進(jìn)制數(shù)轉(zhuǎn)化而成，eg:選1-9個(gè)該物品可一轉(zhuǎn)化成從1，2，4，6，8里的數(shù)字組合，從而轉(zhuǎn)化成01背包）O(n^2logn)
void multi_knapsack2(int n,int W)//二進(jìn)制拆分 {//W為背包容量，，w[i],c[i],p[i]為第i件物品的重量，價(jià)值，數(shù)量for(int i=1;i<=n;i++){if(p[i]*w[i]>=W)//轉(zhuǎn)化成完全背包,因?yàn)檠b不完for(int j=w[i];j<=W;j++)dp[j]=max(dp[j],dp[j-w[i]]+c[i]); else{for(int k=1;p[i]>0;k<<=1)//k=2的0 1 2 3.。。次方,p[i]是物品一開始的數(shù)量也是余數(shù) {int x=min(k,p[i]);//選較小的數(shù)， eg 8=1+2+4+1for(int j=W;j>=w[i]*x;j--)//轉(zhuǎn)化成01背包dp[j]=max(dp[j],dp[j-w[i]*x]+x*c[i]);p[i]-=x;//余數(shù) } }}}（洛谷）櫻花
洛谷）砝碼稱重
（洛谷）Space Elevator 太空電梯（排序+多重背包）
分組背包（洛谷：通天之分組背包）
#include<iostream> #include <algorithm> #include <cstring> using namespace std; int t,n,m,k,dp[1111],ans,w[1111],z[1111],g[1111][1111],b[1111]; int main() {cin>>m>>n;for(int i=1;i<=n;i++){int x;cin>>w[i]>>z[i]>>x;b[x]++;//記錄該組的物品數(shù) t=max(t,x);//記錄一共有多少組g[x][b[x]]=i;//記錄第x組中第b[x]個(gè)物品的編號(hào) }for(int i=1;i<=t;i++){for(int j=m;j>=0;j--)//枚舉容量，巧妙避開了物品沖突 {for(int k=1;k<=b[i];k++)//枚舉第i組的物品{if(j>=w[g[i][k]])dp[j]=max(dp[j],dp[j-w[g[i][k]]]+z[g[i][k]]);} }}cout<<dp[m];return 0; }（洛谷）有線電視網(wǎng)（樹形dp+分組背包+01背包）?
最長(zhǎng)（上升和非上升）公共子序列，，直接看代碼
（洛谷）導(dǎo)彈攔截
求最長(zhǎng)非上升公共子序列和最長(zhǎng)上升公共子序列 記住允許=的（非上升，非下降）用upper，不允許（遞增，遞減）用lower,剛好反過來 #include <iostream> #include <cmath> #include <algorithm> using namespace std; #define ll long long int arr[100007],d1[100007],d2[100007],len1=1,len2=1; ll ans; inline int read() {int a=0,b=1;char ch=getchar();while(ch<'0'||ch>'9'){b*=-1;ch=getchar();}while(ch>='0'&&ch<='9'){a=(a<<3)+(a<<1)+(ch^48);ch=getchar();}return a*b; } int main() {int n=0;while(scanf("%d",&arr[++n])!=EOF);n--;//這里雖然是先++的，但最后還要--d1[1]=arr[1],d2[1]=arr[1];//用d1來存最長(zhǎng)不上升序列 for(int i=2;i<=n;i++){if(d1[len1]>=arr[i])d1[++len1]=arr[i];//如果a[i] <= d[len]，說明a[i]可以接在d后面(而整個(gè)d還是有序的)，那就簡(jiǎn)單粗暴地把a(bǔ)[i]丟進(jìn)delse //如果a[i]>d1[len1]，在d中找到第一個(gè)小于a[i]的數(shù)，刪了，用a[i]替代它 ，就類似前面不選該數(shù){int x=upper_bound(d1+1,d1+len1+1,arr[i],greater<int>())-d1;//greater<int>()把序列變成遞增，upper_bound找第一個(gè)小于a[i]的數(shù) d1[x]=arr[i];//存放最長(zhǎng)非降序公共子序列 }if(d2[len2]<arr[i])d2[++len2]=arr[i];else{int x=lower_bound(d2+1,d2+len2+1,arr[i])-d2; d2[x]=arr[i];//存放最長(zhǎng)上升公共子序列 }}cout<<len1<<endl<<len2;return 0; }（牛客）合唱隊(duì)形（最長(zhǎng)遞增和最長(zhǎng)遞減）?
（洛谷）木棍加工（最長(zhǎng)遞增子序列+貪心，且有點(diǎn)小特殊）
（洛谷）友好城市（很隱晦的最長(zhǎng)上升子序列）
區(qū)間dp
規(guī)律：區(qū)間dp狀態(tài)定義? ?一定是要開兩個(gè)以上維度維護(hù)左區(qū)間和右區(qū)間,eg;dp[i][j]維護(hù)(i,j)區(qū)間
dp[i1][j1][i2][j2]同時(shí)維護(hù)(i1,j1),(i2,j2)區(qū)間
（洛谷）合并石子（弱化版）
區(qū)間dp，，一般版本O(n^3)，一般不會(huì)被卡時(shí) #include <iostream> #include <cstring> #include <algorithm> using namespace std; int arr[302],f[302][302],sum[302]; int main() {int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",arr+i);sum[i]=sum[i-1]+arr[i];}memset(f,0x7f,sizeof(f));//把初始值設(shè)為無窮大***for(int len=1;len<=n;len++)//枚舉區(qū)間長(zhǎng)度 ，，因?yàn)椴恢绤^(qū)間長(zhǎng)度多少合適（有點(diǎn)類似迭代加深搜索）{for(int i=1;i+len-1<=n;i++)//左端 {int j=i+len-1;//右端 if(len==1)f[i][j]=0;else{for(int k=i;k<j;k++)//枚舉中間值，通過小區(qū)間推大區(qū)間（k不能==j，否則k+1>j){int tem=f[i][k]+f[k+1][j]+sum[j]-sum[i-1];//合并i-k和k+1-j和[i-k]-[(k+1)-j]石子的費(fèi)用 if(f[i][j]>tem)f[i][j]=tem;}}}}printf("%d",f[1][n]);return 0; }區(qū)間dp，記憶性搜索版本，復(fù)雜度>一般版本，一般也不會(huì)被卡時(shí)，怎么方便怎么來 include <iostream> #include <cstring> using namespace std; #define maxn 0x7f7f7f7f int arr[302],f[302][302],sum[302]; int dfs(int L,int R) {if(L==R)return f[L][R]=0;//返回0的同時(shí)將f[L][R]值賦為0if(f[L][R]!=maxn)return f[L][R];//算過就返回 for(int k=L;k<=R;k++){int tem=dfs(L,k)+dfs(k+1,R)+sum[R]-sum[L-1];//小區(qū)間推大區(qū)間，算大區(qū)間時(shí)，小區(qū)間不一定有值，所以再調(diào)用dfs if(f[L][R]>tem)f[L][R]=tem;} return f[L][R]; } int main() {int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",arr+i);sum[i]=sum[i-1]+arr[i];}memset(f,0x7f,sizeof(f));//將f初始值設(shè)為0x7f7f7f7f dfs(1,n);printf("%d",f[1][n]);return 0; }（牛客）取數(shù)游戲2（線性dp+區(qū)間dp思想：大區(qū)間推小區(qū)間）
（牛客）合并回文子串（線性dp+區(qū)間dp思想+字符串dp+判定dp）
（洛谷）乘積最大
(洛谷）刪數(shù)（區(qū)間dp思想）
(洛谷）玩具取名（區(qū)間dp（稀有的判定性），且有點(diǎn)難想）
(洛谷）加分二叉樹（區(qū)間dp+二叉樹的中序遍歷轉(zhuǎn)前序遍歷）
環(huán)形區(qū)間dp
（牛客）石子合并
(牛客）凸多邊形的劃分?
#include <iostream> #include <algorithm> #include <cstring> using namespace std; #define ll long long ll arr[300],sum[300]; ll dp1[300][300],dp2[300][300]; int main() {int n;cin>>n;for(int i=1;i<=n;i++)cin>>arr[i],sum[i]=sum[i-1]+arr[i];for(int i=n+1;i<=2*n-1;i++)sum[i] = sum[i - 1] + arr[i - n];memset(dp1,0x3f,sizeof dp1);for(int len=1;len<=n;len++){for(int i=1;i+len-1<=2*n-1;i++){int j=i+len-1;if(len==1)dp2[i][j]=dp1[i][j]=0;else{for(int k=i;k<j&&j<=2*n-1;k++){dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]);dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]);} }}}ll maxn=-1000000;ll minn=0x3f3f3f3f;for(int i=1;i<=n;i++){maxn=max(maxn,dp2[i][i+n-1]);minn=min(minn,dp1[i][i+n-1]);}cout<<minn<<endl<<maxn;return 0; }樹形dp
先dfs子節(jié)點(diǎn)的狀態(tài)，在從下往上推根節(jié)點(diǎn)狀態(tài)
1.（牛客）沒有上司的舞會(huì)
#include <iostream> #include <vector> using namespace std; int n,root=-1,myroot[7000],happy[7000],dp[7000][2];//dp[i][j],i表示節(jié)點(diǎn)序號(hào)，j為0或者1，表示選或不選該節(jié)點(diǎn) vector<int>son[7000]; void tree_dfs(int u) {dp[u][0]=0;dp[u][1]=happy[u];for(int i=0;i<son[u].size();i++){int v=son[u][i];tree_dfs(v);dp[u][1]+=dp[v][0];//若選該結(jié)點(diǎn)，則不選其子節(jié)點(diǎn)dp[u][0]+=max(dp[v][0],dp[v][1]);//若不選該結(jié)點(diǎn)}return; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",happy+i);}for(int i=1;i<=n;i++){int l,k;cin>>l>>k;if(l==0&&k==0)break;myroot[l]=1;//有父節(jié)點(diǎn)son[k].push_back(l);}for(int i=1;i<=n;i++)//找沒有父節(jié)點(diǎn)的，即根節(jié)點(diǎn){if(!myroot[i]){root=i;break;}}tree_dfs(root);cout<<max(dp[root][1],dp[root][0]);return 0; }（洛谷）最大子樹和（很簡(jiǎn)單的樹形dp）
（洛谷）聯(lián)合權(quán)值（不一樣的樹形dp***）?
（洛谷）有線電視網(wǎng)（樹形dp+分組背包(01))經(jīng)典模板
（牛客）Treepath（樹形dp）
（牛客）月之暗面（樹形dp+后置維護(hù)）（沒想出來）
狀壓dp
（牛客）互不侵犯king
狀壓DP-互不侵犯_嗶哩嗶哩_bilibili（直接看代碼也可以。。。）
#include <iostream> #include <algorithm> using namespace std; #define ll long long ll dp[10][1<<9][1000];//第i行，第i行為st的擺放方式，放了k個(gè)國(guó)王的擺放方案數(shù) int n,k; int c(ll st)//返回放了st代表的國(guó)王數(shù) {int sum=0;while(st){if(st%2)sum++;st/=2;}return sum; } bool check1(ll st)//判斷當(dāng)行是否合法 {for(int i=0;i+1<n;i++){if(st & (1<<i) && (st & (1<<(i+1))))return false;//&兩邊為真則為真}return true; } bool check2(ll st,ll st2)//判斷當(dāng)行于其上一行間關(guān)系是否合法 {for(int i=0;i<n;i++){if(st & (1<<i)){if(st2 & (1<<i))return false;else if(i+1<n && (st2 & (1<<(i+1)))) return false;else if(i-1<n && (st2 & (1<<(i-1)))) return false;}}return true; } int main() {scanf("%d %d",&n,&k);for(int i=1;i<=n;i++){for(int st=0;st<(1<<n);st++)//從0開始，為什么st不是<=?因?yàn)?-n-1就有9個(gè)數(shù)了{(lán)if(!check1(st))continue;//若該行擺法方式違法if(i==1)dp[i][st][c(st)]=1;else{for(int j=c(st);j<=k;j++)//枚舉1~i行一共放了的國(guó)王數(shù){for(int st2=0;st2<(1<<n);st2++)//枚舉上一行放國(guó)王位置情況{if(check2(st,st2)&&check1(st2)){dp[i][st][j]+=dp[i-1][st2][j-c(st)];}}}}}}ll ans=0;for(int i=0;i<(1<<n);i++)ans+=dp[n][i][k];//cout<<ans;return 0; }總結(jié)
- 上一篇： VM16虚拟机去虚拟化心得4
- 下一篇： 遥感影像目标检测