石子合并问题（区间dp）

分手后的思念是犯贱 2022-10-11 00:59 278阅读 0赞 
  1. #include <iostream>
  2. using namespace std;
  3. #define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  4. const int N = 310; // O(n^3)
  5. int n;
  6. int s[N], a[N], f[N][N];
  8. void solve(){ 
  9.     memset(f, 0x3f, sizeof(f));
  10.     cin >> n;
  11.     for (int i = 1; i <=n; ++i) { 
  12.         cin >> a[i];
  13.         s[i] = s[i-1] + s[i];
  14.         f[i][i] = 0;
  15.     }
  16.     for (int len = 2; len <= n; ++len)
  17.         for (int l = 1; len+l-1 <= n; ++l)
  18.         { 
  19.             int r = len+l-1;
  20.             for (int k = l; k < r; k++){ 
  21.                 f[l][r] = min(f[l][r], f[l][k]+f[k+1][r]+s[r]-s[l-1]);
  22.             }
  23.         }
  24.     cout << f[1][n];
  25. }
  26. int main()
  27. { 
  28.     ios;
  29.     solve();
  30. }

发表评论

表情：
评论列表 （有 0 条评论，278人围观）

还没有评论，来说两句吧...

相关阅读

    相关 石子合并问题 （区间dp）

    石子合并问题是最经典的DP问题。首先它有如下3种题型： (1)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为新合成的

    叁歲伎倆叁歲伎倆/ 0 赞/ 292 阅读

    相关 282 石子合并（区间dp）

    1. 问题描述： 设有 N 堆石子排成一排，其编号为 1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两

    朱雀朱雀/ 0 赞/ 324 阅读

    相关 ACM DP 石子合并问题

    滴，集训第二十一天打卡。 可能是对组队不太满意，都不大高兴做新的训练... 所以最近一直在磨DP，翻一下博客，发现最近都是DP啊... 这个石子合并的，我做的训练数据n是

    小灰灰小灰灰/ 0 赞/ 291 阅读