总结：区间 DP 进阶

· · 算法·理论

请在阅读时先阅读：区间 DP

相信大家已经学会使用区间 DP 来写题目了，让我们来一些拓展的例题吧：

例题讲解

这道题其实是区间 DP 的变种，与我们写过的那一道合唱队十分相似。

首先定义一个初始状态 f_{i,j} 表示关掉 1 \sim j 的路灯的最小花费，可以发现，如果从中间枚举决策点一定的是不优的，因为从中间走过去时可以顺道关掉一段的灯，所以我们不能枚举决策点，所以就是从两端进行转移。

因为我们其实是不知道老张到底是从那一边过来的，所以我们可以在原有的 f_{i,j} 上在加上一个维度，也即 f_{i,j,0} 与 f_{i,j,1} 分别表示的是老张从 i 这个点开始走，和老张从 j 这个点开始走的花费，然后直接进行转移即可。

代码：

// I don't produce code, I'm just a code mover
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>

using namespace std;

const int kMaxN=50+5,kInf=1e9+7; 

int n,c,dp[kMaxN][kMaxN][2],sum[kMaxN],x[kMaxN],w[kMaxN];

signed main()
{
  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  cin>>n>>c;
  for(int i=1;i<=n;i++) cin>>x[i]>>w[i],sum[i]=sum[i-1]+w[i];
  fill(dp[0][0],dp[n+1][1],kInf);
  dp[c][c][0]=dp[c][c][1]=0;
  for(int len=2;len<=n;len++)
    for(int i=1;i+len-1<=n;i++)
        {
        int j=i+len-1;
            dp[i][j][0]=min(dp[i+1][j][0]+(x[i+1]-x[i])*(sum[i]+sum[n]-sum[j]),dp[i+1][j][1]+(x[j]-x[i])*(sum[i]+sum[n]-sum[j]));
            dp[i][j][1]=min(dp[i][j-1][1]+(x[j]-x[j-1])*(sum[i-1]+sum[n]-sum[j-1]),dp[i][j-1][0]+(x[j]-x[i])*(sum[i-1]+sum[n]-sum[j-1]));
        }   
    cout<<min(dp[1][n][0],dp[1][n][1]); 
    return 0;
}

很显然，这道题其实也是变种，我们发现，这道题其实不是一整个区间 DP，而是在每一层里面均有一个区间 DP。

还是一样的状态，定义 f_{l,i,j} 为第 l 层 i \sim j 区间内的摆法数量，其实就是判断一下，将上一层的所有和全部加入到其中去。

然后我们发现，如果不加任何的优化，那么时间复杂度为 n^5 直接爆炸了，所以我们可以加上一个二位前缀和进行优化，然后直接转移即可。

代码：

// I don't produce code, I'm just a code mover
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int kMaxN=100+5,kMod=1e9+7,kInf=1e9+10;

int n,m,dp[kMaxN][kMaxN][kMaxN],vis[kMaxN][kMaxN],sum[kMaxN][kMaxN],ans; 
char c[kMaxN][kMaxN];

signed main()
{
  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=n;i>=1;i--)
    for(int j=1;j<=m;j++) cin>>c[i][j],vis[i][j]=vis[i][j-1]+(c[i][j]=='X');
  dp[0][1][m]=1;
  for(int l=1;l<=n;l++)
  {
    for(int i=1;i<=m;i++)    
      for(int j=1;j<=m;j++) sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[l-1][i][j])%kMod;  
    for(int i=1;i<=m;i++)
      for(int j=i;j<=m;j++) 
        if(!(vis[l][j]-vis[l][i-1])) dp[l][i][j]=(sum[i][m]-sum[i][j-1]+kMod)%kMod;
  }
  for(int l=1;l<=n;l++)
    for(int i=1;i<=m;i++)
      for(int j=i;j<=m;j++) ans=(ans+dp[l][i][j])%kMod;
  cout<<ans+1;
  return 0;
}

这道题是区间 DP 的一个思维难题。

首先这个状态其实是一样的，那么这里我们就不多说了，但是转移就非常离谱。

首先我们不考虑折叠，那么我们可以直接转移过来，也就是 f_{i,j} = \min (f_{i,j} f_{i,k} + f_{k+1,j})，但是其它的话，我们其实可以用一个 Check 函数判断当前是否可以直接折叠，然后我们枚举长度，直接进行转移就可以了。

代码：

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 100 + 5, kInf = 1000000000 + 7;

string s;
int n, f[kMaxN][kMaxN];

bool Check(string S, int l) {
  if (S.size() % l != 0) return false;
  string c = S.substr(0, l);
  for (int i = 0; i + l - 1 < S.size(); i += l) 
    if (S.substr(i, l) != c) return false;
  return true;
}

int main() {
  cin >> s;
  n = s.size(), s = " " + s;
  fill(f[0], f[n + 1], kInf);
  for (int i = 1; i <= n; i++) f[i][i] = 1;
  for (int l = 2; l <= n; l++) {
    for (int i = 1; i + l - 1 <= n; i++) {
      int j = i + l - 1;  
      for (int k = i; k < j; k++) f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
      for (int L = 1; L <= l; L++) 
        if (Check(s.substr(i, l), L)) f[i][j] = min(f[i][j], f[i][i + L - 1] + 2 + (int)to_string(l / L).size());
    }
  }
  cout << f[1][n];
  return 0;
}

还是一样，我们定义 f_{i,j} 为消除 i \sim j 的最大价值。

但是我们可以发现，比如我们可能在删除一个部分后，遇到在前面的答案中不删某个值，让那个答案和后面的合并能造成更大的答案。所以我们就要重新定义。

这就出现了 DP 最忌讳的后效性，所以我们需要重新定义状态。

我们重新定义：f_{i,j,k} 表示将区间 i 到 j 消除后再把 j 后面的 k 个也消除的最大价值。

然后直接预处理后缀和，然后对区间枚举往后 k 个进行转移即可。

代码：

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 50 + 10;
const int MOD = 1e9 + 7;
const int INF = 1e18;

int n;
int color[N];
int num[N];
int suf[N];
int f[N][N][1000 + 5];

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> color[i];
  for (int i = 1; i <= n; i++) cin >> num[i];
  for (int i = 1; i <= n; i++) 
    for (int j = i + 1; j <= n; j++) 
      if (color[i] == color[j]) suf[i] += num[j];
  for (int i = 1; i <= n; i++) 
    for (int j = 0; j <= suf[i]; j++) f[i][i][j] = (num[i] + j) * (num[i] + j);
  for (int len = 2; len <= n; len++) {
    for (int i = 1; i + len - 1 <= n; i++) {
      int j = i + len - 1;
      for (int k = 0; k <= suf[j]; k++) f[i][j][k] = max(f[i][j][k], f[i][j - 1][0] + (num[j] + k) * (num[j] + k));
      for (int k = i; k < j - 1; k++) 
        if (color[k] == color[j]) 
          for (int t = 0; t <= suf[j]; t++)  f[i][j][t] = max(f[i][j][t], f[i][k][num[j] + t] + f[k + 1][j - 1][0]);
    }
  }
  cout << f[1][n][0] << '\n';
  return 0;
}