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://zerojudge.tw/ShowProblem?problemid=d686 也是區間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,l;      while (cin >> l && l)     {         cin >> n;         vector <int>   v (n + 1 );         vector < vector <int>>   dp (n + 2 , vector <int> (n + 2 ));          for ( int  i = 1 ;i <= n;i ++ ) cin >> v[i];     ...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d652 區間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 <int>   v (n + 1 );     vector < vector <int>>   dp (n + 1 , vector <int> (n + 1 , 1 e 9 ));      for ( int  i = 1 ;i <= n;i ++ ) cin >> v[i];      for ( int  i = 1 ;i < n;i ++ )         dp[i][i] = dp[i][i + 1 ] = 0 ;      for ( int  i = 1 ;i < n;i ++ ) ...