AcWing基礎算法課Level-2 第五講 動態規劃
背包問題
AcWing 2. 01背包問題3018人打卡
AcWing 3. 完全背包問題2749人打卡
AcWing 4. 多重背包問題2552人打卡
AcWing 5. 多重背包問題 II2312人打卡
AcWing 9. 分組背包問題2276人打卡
線性DP
AcWing 898. 數字三角形2531人打卡
AcWing 895. 最長上升子序列2545人打卡
AcWing 896. 最長上升子序列 II1846人打卡
AcWing 897. 最長公共子序列2305人打卡
AcWing 902. 最短編輯距離1893人打卡
AcWing 899. 編輯距離1630人打卡
區間DP
AcWing 282. 石子合并2092人打卡
計數類DP
AcWing 900. 整數劃分1609人打卡
數位統計DP
AcWing 338. 計數問題818人打卡
狀態壓縮DP
AcWing 291. 蒙德里安的夢想1252人打卡
AcWing 91. 最短Hamilton路徑1219人打卡
樹形DP
AcWing 285. 沒有上司的舞會1404人打卡
記憶化搜索
AcWing 901. 滑雪1470人打卡
AcWing 2. 01背包問題
//dp[i+1][j]:從0到i+1這個物品中選出總重量不超過j的物品時總價值的最大值 #include #include using namespace std; int n, s, w[5050], k[5050], dp[5050][5050]; int main(){ cin>>n>>s; for(int i = 0; i < n; i++)cin>>w[i]>>k[i]; for(int i = 0; i < n; i++){ for(int j = 0; j <= s; j++){ if(w[i] <= j)dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+k[i]); else dp[i+1][j] = dp[i][j]; } } cout<AcWing 3. 完全背包問題
//k*v[i]<=j時枚舉選k次，用來更新狀態 //f[i][j]:從0到i個這些物品中選出總重量不超過j的物品時總價值的最大值 #include using namespace std; const int maxn = 1010; int v[maxn], w[maxn]; //int f[maxn][maxn]; int f[maxn]; int main(){ int n, m; cin>>n>>m; for(int i = 1; i <= n; i++) cin>>v[i]>>w[i]; /*1.TLE for(int i = 1; i <= n; i++) for(int j = 0; j <= m; j++) for(int k = 0; k*v[i]<=j; k++) f[i][j] = max(f[i][j], f[i-1][j-k*v[i]]+k*w[i]); */ /*2.MLE for(int i = 1; i <= n; i++){ for(int j = 0; j <= m; j++){ f[i][j] = f[i-1][j]; if(j-v[i]>=0)//從f[i]選，可以無限選 f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]); } } cout<AcWing 4. 多重背包問題
//拆成01背包 #include using namespace std; const int maxn = 10100; int v[maxn], w[maxn], t; int f[maxn]; int main(){ int n, m; cin>>n>>m; for(int i = 1; i <= n; i++){ int x, y, s; cin>>x>>y>>s; while(s--){ v[++t]=x; w[t]=y; } } for(int i = 1; i <= t; i++) for(int j = m; j >= v[i]; j--) f[j] = max(f[j], f[j-v[i]]+w[i]); cout<AcWing 5. 多重背包問題 II
//2進制優化，復雜度從O(n*s*m)優化到O(n*logs*m) //在一堆蘋果選出n個蘋果,傳統的解法是一個一個地去選,選夠n個蘋果就停止。這樣選擇的次數就是n次。現在將這一堆蘋果分別按照1,2,4,8,16,.....512分到10個箱子里，那么現在任何一個數字x，都可以用著10堆蘋果表示，選擇次數<=10 #include using namespace std; const int maxn = 10100; int v[maxn], w[maxn], t; int f[maxn]; int main(){ int n, m; cin>>n>>m; for(int i = 1; i <= n; i++){ int a, b, s; cin>>a>>b>>s; for(int k = 1; k <= s; k *= 2){ v[++t] = a*k; w[t] = b*k; s -= k; } if(s>0){v[++t]=a*s; w[t]=b*s;} } for(int i = 1; i <= t; i++) for(int j = m; j >= v[i]; j--) f[j] = max(f[j],f[j-v[i]]+w[i]); cout<AcWing 9. 分組背包問題
//按照組來轉移，每次枚舉第i組中所有元素為上一組進行轉移即可 //f[i][j]:從0到i組物品中選出總重量不超過j的物品時總價值的最大值 #include using namespace std; const int maxn = 110; int v[maxn][maxn], w[maxn][maxn], s[maxn]; int f[maxn][maxn]; int main(){ int n, m; cin>>n>>m; for(int i = 1; i <= n; i++){ cin>>s[i]; for(int j = 1; j <= s[i]; j++) cin>>v[i][j]>>w[i][j]; } for(int i = 1; i <= n; i++){ for(int j = 0; j <= m; j++){ f[i][j] = f[i-1][j]; //不選 for(int k = 1; k <= s[i]; k++){ if(j>=v[i][k]){ f[i][j] = max(f[i][j], f[i-1][j-v[i][k]]+w[i][k]); } } } } cout<AcWing 898. 數字三角形
//f[i][j]:從(i,j)出發能獲得的最大值 _裸遞推 #include #include using namespace std; int n, a[510][510], f[510][510]; int main(){ cin>>n; for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) cin>>a[i][j]; for(int i = n; i >= 1; i--) for(int j = 1; j <= i; j++) f[i][j] = max(f[i+1][j], f[i+1][j+1])+a[i][j]; cout<AcWing 895. 最長上升子序列
//f[i]:到i為止的LIS的長度。 //f[i]=max{1,f[j]+1|j #include using namespace std; int n, a[1010], f[1010], ans; int main(){ cin>>n; for(int i = 1; i <= n; i++)cin>>a[i]; for(int i = 1; i <= n; i++){ int t = 0; for(int j = 1; j < i; j++) if(a[j]AcWing 896. 最長上升子序列 II
//f[i]:長為i的LIS末位的最小值 #include #include #include using namespace std; int f[1000010]; int main(){ memset(f,0x3f,sizeof(f)); int n; cin>>n; for(int i = 1; i <= n; i++){ int x; cin>>x; *lower_bound(f+1,f+n+1,x) = x; } cout<AcWing 897. 最長公共子序列
//f[i][j]表示到a[i]和b[j]為止的lCS。轉移，顯而易見。 #include using namespace std; int f[1010][1010]; int main(){ int n, m; cin>>n>>m; string a, b; cin>>a>>b; for(int i = 0; i < a.size(); i++){ for(int j = 0; j < b.size(); j++){ if(a[i]==b[j])f[i+1][j+1] = f[i][j]+1; else f[i+1][j+1] = max(f[i][j+1],f[i+1][j]); } } cout<AcWing 902. 最短編輯距離
//題意：給出兩個字符串a和b，將a通過刪除，插入，替換變換成b，求最少操作次數。 //思路：f[i][j]表示將a[1~i]變成b[1~j]的最小操作次數，轉移的時候分別考慮刪除，插入和替換即可。 #include using namespace std; const int maxn = 1010; int f[maxn][maxn]; int main(){ int n, m; string a, b; cin>>n>>a>>m>>b; a = "0"+a; b = "0"+b; memset(f,0,sizeof(f)); for(int i = 1; i <= n; i++)f[i][0] = i;//只能刪除 for(int i = 1; i <= m; i++)f[0][i] = i;//只能插入 for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);//刪除a[i]或插入b[j]使之匹配, 次數+1 if(a[i]==b[j])f[i][j] = min(f[i][j],f[i-1][j-1]);//本來就相等 else f[i][j] = min(f[i][j],f[i-1][j-1]+1);//修改a[i]或b[j] } } cout<AcWing 899. 編輯距離
//題意：給出n個字符串和m個詢問，每次詢問n個串中有多少個可以在k次操作(插入, 刪除, 替換)內變成給出的字符串t //思路：多跑幾遍上題的最短編輯距離就行,m*(n*10^2)=1e8 #include using namespace std; const int maxn = 1010; string s[maxn]; //計算次數 int f[maxn][maxn]; int dist(string a, string b){ int n=a.size(), m=b.size(); a = "0"+a; b = "0"+b; //memset(f,0,sizeof(f)); for(int i = 1; i <= n; i++)f[i][0] = i;//只能刪除 for(int i = 1; i <= m; i++)f[0][i] = i;//只能插入 for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);//刪除a[i]或插入b[j]使之匹配, 次數+1 if(a[i]==b[j])f[i][j] = min(f[i][j],f[i-1][j-1]);//本來就相等 else f[i][j] = min(f[i][j],f[i-1][j-1]+1);//修改a[i]或b[j] } } return f[n][m]; } int main(){ ios::sync_with_stdio(false); int n, m; cin>>n>>m; for(int i = 1; i <= n; i++)cin>>s[i]; for(int i = 1; i <= m; i++){ string t;int k; cin>>t>>k; int ans = 0; for(int i = 1; i <= n; i++) if(dist(s[i], t) <= k)ans++; cout<AcWing 282. 石子合并
#include #include using namespace std; const int maxn = 1010, inf=0xffffff; int w[maxn], f[maxn][maxn]; int main(){ int n; cin>>n; for(int i = 1; i <= n; i++)cin>>w[i]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) f[i][j] = i==j ? 0 : inf; for(int i = 1; i <= n; i++)w[i] += w[i-1]; //轉移順序長度從小到大覆蓋即可 for(int i = n; i >= 1; i--)//枚舉起點 for(int j = i; j <= n; j++)//枚舉終點 for(int k = i; k <= j; k++)//枚舉斷點 f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+w[j]-w[i-1]); cout<AcWing 900. 整數劃分
//題意：給出一個整數n，求其有多少種形如n==n1+n2+..nk的分法，輸出劃分總數%1e9+7; //思路：把1,2,3,...,n分別看做n個物體的體積,這n個物體均無使用次數限制,問恰好能裝滿總體積為n的背包的總方案數（完全背包問題變形）。f[i][j]表示用[1-i]的整數拼成j的方案數，轉移時考慮能不能選并把值累加一下就行。 #include using namespace std; const int maxn = 1010; const int mod = 1e9+7; int f[maxn][maxn]; int main(){ ios::sync_with_stdio(false); int n; cin>>n; for(int i = 0; i <= n; i++)f[i][0] = 1;//前i個全不選也是一種方案 for(int i = 1; i <= n; i++){//考慮第i個數選不選 for(int j = 1; j <= n; j++){//能拼成數j的方案數 if(j >= i)f[i][j] = (f[i-1][j]+f[i][j-i])%mod;//能選 else f[i][j] = f[i-1][j]%mod;//不能選 } } cout<AcWing 338. 計數問題
//題意：給出兩個數a和b，求a和b之間所有數字中0-9的出現次數，a,b<=1e8 //思路：可以通過找規律推出1-n中數字i出現的次數，然后作差。 #include using namespace std; //計算從1到n的整數中數字i出現多少次 int cal(int n, int i){ int len = 0, t=n; while(t){len++; t/= 10;} //計算位數 int ans = 0; //從右到左第j位上(個十百千)，數字i出現多少次 for(int j = 1; j <= len; j++){ //計算第j-1,j,j+1位的數字 int p = pow(10,j-1); int l = n/p/10, r = n%p, dj = n/p%10; //第j位左邊的數字小于實際l的情況 if(i)ans += l*p; if(!i && l)ans += (l-1)*p; //第j位左邊的數字等于實際l的情況 if((dj>i) && (i||l))ans += p; if((dj==i) && (i||l))ans += r+1; } return ans; } int main(){ ios::sync_with_stdio(false); int a, b; while(cin>>a>>b){ if(a==0 && b==0)break; if(a>b)swap(a,b); for(int i = 0; i <= 9; i++) cout<AcWing 291. 蒙德里安的夢想
/* 題意：把n*m的棋盤分成若干個1*2的長方形，求有多少種方案 思路：首先總的方案數,等價于橫著擺放的方案數，所以直接枚舉橫著的就行。然后如何判斷當前方案數是否合法？所有剩余位置能否填充滿豎著的小方塊。可以按列來看，每一列內部所有連續的空著的小方塊需要是偶數個。 狀態：f[i][j]表示已經將前i-1列擺好，且從第i?1列，伸出到第i列的狀態是j的所有方案，其中j是一個2進制數，表示當前第i列的狀態。 狀態轉移：枚舉第(i-1,i)的所有狀態j和(i-2,i-1)的所有狀態k，如果他們兩個不沖突，那就可以從f[i-1,k]轉移到f[i,j]。 */ #include using namespace std; typedef long long LL; const int maxn=12; LL ok[1<<12], f[12][1<<12]; int main(){ int n, m; while(cin>>n>>m &&n&&m){ //判斷狀態i是否合法 for(int i = 0; i < (1<>j)&1==1){ if(cnt%2==1)ok[i]=false; cnt = 0; }else cnt++; } if(cnt%2==1)ok[i] = false; } //dp memset(f,0,sizeof(f)); f[0][0] = 1; for(int i = 1; i <= m; i++){ for(int j = 0; j < (1<AcWing 91. 最短Hamilton路徑
//f[i][j]表示當前已經走過點的集合為i，當前人站在j（終點），此時的最短路徑長度 //轉移時用不包含j的集合向當前集合轉移，用集合內的點k和邊e[k][j]來更新，f[i][j] = min{f[i][j], f[i-(1< using namespace std; const int maxn=30; int e[maxn][maxn], f[1<<20][maxn]; int main(){ ios::sync_with_stdio(false); int n; cin>>n; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin>>e[i][j]; memset(f,0x3f,sizeof(f)); f[1][0] = 0; for(int i = 0; i < (1<>j&1)==1){//j在集合里 for(int k = 0; k < n; k++){ if(((i-(1<>k&1)==1){//走到j這個點之前,以k為終點的最短距離 f[i][j] = min(f[i][j], f[i-(1<AcWing 285. 沒有上司的舞會
/* 用f[x][0],f[x][1] 分別表示x沒去和去了的最大價值。 f[x][0] = sigmar:max(f[y][0],f[y][1]); f[x][1] = sigmar:f[y][0]; */ #include #include #include #define maxn 6000*2 using namespace std; int n, r[maxn], f[maxn][2], in[maxn]; vectorG[maxn]; void dp(int x){ f[x][1] = r[x]; for(int i = 0; i < G[x].size(); i++){ int y = G[x][i]; dp(y); f[x][0] += max(f[y][0],f[y][1]); f[x][1] += f[y][0]; } } int main(){ cin>>n; for(int i = 1; i <= n; i++)cin>>r[i]; for(int i = 1; i < n; i++){ int a, b; cin>>a>>b; G[b].push_back(a); in[a]++; } int head = 0; //找樹根,即入度為0的結點 for(int i = 1; i <= n; i++) if(in[i]==0){ head = i; break; } dp(head); cout<AcWing 901. 滑雪
//f[i][j]:以(i,j)為終點的最長路是是多少 //f[i][j] = f(它四周的比他高的方塊的最長路)+1 #include #include using namespace std; const int maxn = 550; int r, c, a[maxn][maxn], f[maxn][maxn], ans; const int dx[] = {1,0,-1,0}; const int dy[] = {0,-1,0,1}; bool inside(int x, int y){return x>=1&&x<=r&&y>=1&&y<=c;} int dp(int x, int y){ if(f[x][y])return f[x][y]; int res = 0; for(int i = 0; i < 4; i++){ int nx = x+dx[i], ny = y+dy[i]; if(inside(nx,ny)&&a[nx][ny]>a[x][y]){ res = max(res,dp(nx,ny)); } } return f[x][y]=res+1;//我竟然因為沒有更新f[x][y]導致第二個點沒過。。 } int main(){ ios::sync_with_stdio(false); cin>>r>>c; for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) cin>>a[i][j]; for(int i = 1; i <= r; i++) for(int j = 1; j <= c; j++) ans = max(ans,dp(i,j)); cout<
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
