20250908区间DP总结

引子

全班(倒数)第一个交总结的人。

区间DP

顾名思义，就是在区间里面作区间DP。

该DP用来解决区间最值问题，令dp[i][j]表示区间[i,j]的所有元素的权值和，那么dp[i][j]=dp[i][k]+dp[k+1][j](i-1<k<j)。

区间动态规划（DP）具有以下典型特征：

1. 合并特性：核心操作是将多个子区间合并为一个整体，该过程具有可逆性

2. 问题分解：能够将原问题拆解为可合并的子问题形式

3. 求解方法：

   • 为整个问题设定最值目标
   • 通过枚举所有可能的合并点
   • 将问题划分为左右两个子区间
   • 通过合并子区间得到最优解

A 石子合并（弱化版）

区间DP模板中的模板。

#include<bits/stdc++.h>usingnamespacestd;ints[305],dp[305][305];//前缀和数组和DP数组intmain(){intn;cin>>n;for(inti=1;i<=n;i++){intx;cin>>x;s[i]=s[i-1]+x;}memset(dp,0x3f,sizeof(dp));for(inti=1;i<=n;i++){dp[i][i]=0;//长度为一的区间无需合并,代价为0}for(intlen=2;len<=n;len++){//枚举区间长度for(intl=1;l<=n-len+1;l++){//枚举右节点intr=l+len-1;//左节点for(intk=l;k<r;k++){//中截点dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);//要加上该区间的总和}}}cout<<dp[1][n];return0;}

B Treats for the Cows G/S

见代码注释。

#include<bits/stdc++.h>usingnamespacestd;inta[2005],dp[2005][2005];intdih(intl,intr,intdep){//记忆化搜索if(l>r)return0;if(dp[l][r])returndp[l][r];//记忆化dp[l][r]=max(dih(l+1,r,dep+1)+dep*a[l],dih(l,r-1,dep+1)+dep*a[r]);//要么吃左边，要么吃右边returndp[l][r];}intmain(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}cout<<dih(1,n,1);return0;}