Mirror的演算法筆記

題目鏈接: https://atcoder.jp/contests/dp/tasks/dp_n 區間DP 將史萊姆切為左右兩邊求哪個範圍內的史萊姆相加會最少 注意要從小範圍往大範圍轉移 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using   namespace   std ; using   namespace   __gnu_cxx ; using   namespace   __gnu_pbds ; using   ll   =   long   long ; #define   AC   ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int   main () {     AC      int  n;     cin >> n;     vector < ll >   v (n + 1 ), sum (n + 1 );     vector < vector < ll >>   dp (n + 1 , vector <ll> (n + 1 ));      for ( int  i = 1 ;i <= n;i ++ ) cin >> v[i],sum[i] = sum[i - 1 ] + v[i];      for ( int  i = 1 ;i < n;i ++ )          for ( int  j = 1 ;j + i <= n;j ++ )  ...

題目鏈接: https://atcoder.jp/contests/dp/tasks/dp_g 這題我一開始還傻傻的用Floyd去解 結果爆了 後來看解答說是拓撲排序....... 怎麼會沒想到呢 知道是拓撲就很好做啦 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std; using namespace __gnu_cxx; using namespace __gnu_pbds; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,m,r = 0 ; cin >> n >> m; vector < vector <int>> v (n + 1 ); vector <int> deg (n + 1 , 0 ), dis (n + 1 , 0 ); for ( int i = 0 ;i < m;i ++ ) { int s,t; cin >> s >> t; v[s]. emplace_back (t); deg[t] ++ ; } queue <int> q; for ( int i = 1 ;i < v. size ();i ++ ) if ( ! deg[i]) q. push (i); while (q. size ()) { for ( auto e:v[q. front ()]) { dis[e] = max (dis[e],dis[q. front ()] + 1 ); r = max (r,dis[e]); deg[e] -- ; ...

題目鏈接: https://atcoder.jp/contests/dp/tasks/dp_f 回溯求LCS的解答 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using   namespace   std ; using   namespace   __gnu_cxx ; using   namespace   __gnu_pbds ; using   ll   =   long   long ; #define   AC   ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int   main () {     AC     string s,t,r = "" ;     cin >> s >> t;      int  a = s. size (),b = t. size ();     vector < vector <int>>   dp (s. size () + 1 , vector <int> (t. size () + 1 , 0 ));      for ( int  i = 1 ;i <= s. size ();i ++ )          for ( int  j = 1 ;j <= t. size ();j ++ )              if (s[i - 1 ] == t[j - 1 ]) dp[i]...

題目鏈接: https://atcoder.jp/contests/dp/tasks/dp_d 裸0/1背包問題 以下為code #include < bits/stdc++.h > using namespace std ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,w; cin >> n >> w; vector < ll > dp (w + 1 , 0 ); for ( int i = 0 ;i < n;i ++ ) { int wei,val; cin >> wei >> val; for ( int j = w;j >= wei;j -- ) dp[j] = max (dp[j],dp[j - wei] + val); } cout << dp[w] << ' \n ' ; }

題目鏈接: https://atcoder.jp/contests/dp/tasks/dp_e 這題還蠻有趣的 他的重量開到10⁹導致不能用上一題(常規0/1背包)的做法去做 要把價值當做dp轉移,去找當前價值所需的最小重量 最後找到的最大的小於重量限制的價值就是答案 以下為code #include < bits/stdc++.h > using namespace std ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,w,r = 0 ; cin >> n >> w; vector < ll > dp ( 100001 , 1 e 10 ); dp[ 0 ] = 0 ; for ( int i = 0 ;i < n;i ++ ) { int wei,val; cin >> wei >> val; for ( int j = 100000 ;j >= val;j -- ) dp[j] = min (dp[j],dp[j - val] + wei); } for ( int i = 1 ;i < dp. size ();i ++ ) if (dp[i] <= w) r = i; cout << r << ' \n ' ; }

題目鏈接: https://atcoder.jp/contests/dp/tasks/dp_c 這題開個二維,分成三種case去考慮會比較容易 dp[i][j] , i為第幾天 , j為第幾種活動 轉移曲線如下 dp[i][0]=max(dp[i-1][1],dp[i-1][2])+v[i][0]; dp[i][1]=max(dp[i-1][0],dp[i-1][2])+v[i][1]; dp[i][2]=max(dp[i-1][1],dp[i-1][0])+v[i][2]; 以下為code #include < bits/stdc++.h > using namespace std ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,a,b,c; cin >> n; vector < vector <int>> v (n, vector <int> ( 3 )), dp (n, vector <int> ( 3 )); for ( int i = 0 ;i < n;i ++ ) for ( int j = 0 ;j < 3 ;j ++ ) cin >> v[i][j]; dp[ 0 ][ 0 ] = v[ 0 ][ 0 ],dp[ 0 ][ 1 ] = v[ 0 ][ 1 ],dp[ 0 ][ 2 ] = v[ 0 ][ 2 ]; for ( int i = 1 ;i < n;i ++ ) { dp[i][ 0 ] = max (dp[i - 1 ][ 1 ],dp[i - 1 ][ 2 ]) + v[i][ 0 ]; dp[i][ 1 ] = max (dp[i - 1 ][ 0 ],dp[i - 1 ][ 2 ]) + v[i][ 1 ]; dp[i][ 2 ] = max (dp[i - 1 ][ 1 ],dp[i - 1 ][...

題目鏈接: https://atcoder.jp/contests/dp/tasks/dp_b 這題是A-Frog 1的加強版 不過多一個迴圈還是輕鬆解決 以下為code #include < bits/stdc++.h > using namespace std ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,k; cin >> n >> k; vector <int> v (n), dp (n, 1 e 9 ); for ( int i = 0 ;i < n;i ++ ) cin >> v[i]; dp[ 0 ] = 0 ; for ( int i = 1 ;i < n;i ++ ) for ( int j = 1 ;j <= k;j ++ ) if (i - j >= 0 ) dp[i] = min (dp[i - j] + abs (v[i] - v[i - j]),dp[i]); cout << dp[n - 1 ] << ' \n ' ; }

題目鏈接: https://atcoder.jp/contests/dp/tasks/dp_a 這題就基本DP題 以下為code #include<bits/stdc++.h> using namespace std; using ll = long long; #define AC ios::sync_with_stdio(0),cin.tie(0); int main() { AC int n; cin>>n; vector<int> v(n),dp(n); for(int i=0;i<n;i++) cin>>v[i]; dp[0]=0,dp[1]=abs(v[1]-v[0]); for(int i=2;i<n;i++) dp[i]=min(dp[i-1]+abs(v[i]-v[i-1]),dp[i-2]+abs(v[i]-v[i-2])); cout<<dp[n-1]<<'\n'; } #include<bits/stdc++.h> using namespace std; using ll = long long; #define AC ios::sync_with_stdio(0),cin.tie(0); int main() { AC int n; cin>>n; vector<int> v(n),dp(n); for(int i=0;i<n;i++) cin>>v[i]; dp[0]=0,dp[1]=abs(v[1]-v[0]); for(int i=2;i<n;i++) dp[i]=min(dp[i-1]+abs(v[i]-v[i-1]),dp[i-2]+abs(v[i]-v[i-2])); cout<<dp[n-1]<<'\n'; } #include<bits/stdc++.h> using namespace std; using ll = lon...