当前位置：首页 > news >正文

DP(4)--区间DP

news 2025/7/18 18:33:19

将n(1≤n≤200)堆石子绕圆形操场摆放，现要将石子有次序地合并成一堆。
规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
(1)选择一种合并石子的方案，使得做n-1次合并，得分的总和最小。
(2)选择一种合并石子的方案，使得做n-1次合并，得分的总和最大
输入
4
4 5 9 4
输出
43
54

线性结构是N个数据元素以有序的方式排列。访问线性结构一般采用由前至后的遍历方法。
线性动态规划就是在线性数据的基础上，通过某种递推方式（状态转移方程）得到最终结构的一种规划算法。
sum[i]: 从第1堆到第i堆石子数总和
fmax[i][j]: 从第i堆石子合并到第j堆石子的最大得分
fmin[i][j]: 从第i堆石子合并到第j堆石子的最小得分

初始化： fmax[i][i] = 0, fmin[i][i]= INF
状态方程：
fmax[i][j] = max{fmax[i][k]+fmax[k+1][j]+sum[j]-sum[i-1]} i <= k < j
fmin[i][j] = min{fmin[i][k]+fmin[k+1][j]+sum[j]-sum[i-1]} i <= k < j

由于题中围成一个环，我们将这条链再延长一倍，变成2*n堆，地中第i堆与第n+i堆相同，
动态规划求解后，答案为f(1,n), f(2,n+1), ... , f(n-1,2*n-2)中的最优解

状态转移
要计算f(i,j)的值时需知道所有f(i,k)和f(k+1,j)的值，
以len=j-i+1作为DP 的区间长度，从小到大枚举len，
然后枚举i的值，根据len和i用公式计算出j的值，然后枚举k，时间复杂度为O(n^3)

/* https://loj.ac/problem/10147 */
#include <iostream>
using namespace std;

const int MAXN = 201;
const int INF = 0x3f3f3f3f;
int arr[2*MAXN];
int sum[2*MAXN];
int fmax[2*MAXN][2*MAXN];
int fmin[2*MAXN][2*MAXN];

int main()
{
   int i, j, k, n, len;
   cin >> n;
   for (i = 1; i <= n; ++i)
   {
       cin >> arr[i];
       arr[n+i] = arr[i];
   }
   for (i = 1; i <=(n<<1); ++i)
       sum[i] = sum[i-1] + arr[i];

   for (len = 2; len <= n; ++len)
       for (i = 1; i <= (n<<1)-len+1; ++i)
       {
           j = i + len - 1;
           // 初始化
           fmax[i][j] = 0;
           fmin[i][j] = INF;
           for (k = i; k < j; ++k)
           {
               fmax[i][j] = max(fmax[i][j], fmax[i][k] + fmax[k+1][j] + sum[j] - sum[i-1]);
               fmin[i][j] = min(fmin[i][j], fmin[i][k] + fmin[k+1][j] + sum[j] - sum[i-1]);
           }
       }

   int ansmax = 0, ansmin = INF;
   for (i = 1; i < n; ++i)
   {
       ansmax = max(ansmax, fmax[i][i+n-1]);
       ansmin = min(ansmin, fmin[i][i+n-1]);
   }

cout << ansmin << endl << ansmax << endl;

return 0;
}

四边形不等式优化请参考

https://oi-wiki.org/dp/opt/quadrangle/

https://www.cnblogs.com/a1b3c7d9/p/10984353.html

dp[i][j]=min{dp[i][k]+dp[k+1][j]+w[i][j]} (i≤k<j)
把dp[i][k]+dp[k+1][j]取得最值的那个k, 称为dp[i][j]的最优决策点。

#include <iostream>
using namespace std;
const int MAXN = 201;
const int INF = 0x3f3f3f3f;
int arr[2*MAXN];
int sum[2*MAXN];
int fmax[2*MAXN][2*MAXN];
int fmin[2*MAXN][2*MAXN];
int ma[2*MAXN][2*MAXN]; //ma[i][j]：从第i堆石子合并到第j堆石子的最大得分时的最优决策点
int mi[2*MAXN][2*MAXN]; //mi[i][j]：从第i堆石子合并到第j堆石子的最小得分时的最优决策点

int main()
{
   int i, j, k, n, len, t;
   cin >> n;
   for (i = 1; i <= n; ++i)
   {
       cin >> arr[i];
       arr[n+i] = arr[i];
   }
   for (i = 1; i <=(n<<1); ++i)
   {
       sum[i] = sum[i-1] + arr[i];
       ma[i][i] = i;
       mi[i][i] = i;
   }

   for (len = 2; len <= n; ++len)
       for (i = 1; i <= (n<<1)-len+1; ++i)
       {
           j = i + len - 1;
           // 初始化
           fmax[i][j] = 0;
           fmin[i][j] = INF;
           // 四边形不等式优化
           for (k = ma[i][j-1]; k <= ma[i+1][j] && k < j; ++k)
           {
               t = fmax[i][k] + fmax[k+1][j] + sum[j] - sum[i-1];
               if (fmax[i][j] < t)
               {
                   fmax[i][j] = t;
                   ma[i][j] = k;
               }
           }

           for (k = mi[i][j-1]; k <= mi[i+1][j] && k < j; ++k)
           {
               t = fmin[i][k] + fmin[k+1][j] + sum[j] - sum[i-1];
               if (fmin[i][j] > t)
               {
                   fmin[i][j] = t;
                   mi[i][j] = k;
               }
           }
       }

   int ansmax = 0, ansmin = INF;
   for (i = 1; i < n; ++i)
   {
       ansmax = max(ansmax, fmax[i][i+n-1]);
       ansmin = min(ansmin, fmin[i][i+n-1]);
   }

cout << ansmin << endl << ansmax << endl;

return 0;
}

查看全文

http://www.lryc.cn/news/23397.html