Dp的优化

单调栈优化Dp

The Great Wall II

题意：

给你 n个点，问分成 1∼n 组，每一组的代价就是这一组中的最大值，问每一种情况的最小权值和。

思路：

把状态定义为 d i j 表示 走到 i 号点了 分了j 组的最小代价。

那么先枚举分成了几组 ，枚举从哪个点转移。

d[i][j]=min(d[i][j],d[k][j-1]+max(a[k+1]......a[i]));

这样的暴力的复杂度是 n^3的，考虑怎么优化。

首先 max(1 ~ j)这个肯定是单调递增的，然后如果碰到一个比较大的点，比前面的都大的情况的话，最优的转移肯定是找到前面 \(d[k][j-1]\)的最小值，因为当前的所有的额外权值是固定的，所以前面的这个越小，总价值就越小。所以用单调栈维护一个 权值 递增的单调栈，也就是 后面这个max 的这一半，同时维护一个单调栈中弹出来的最小的 dp 值，也就是说 如果一个大权值放到栈里面，弹出来这些值可以也可以作为转移的点。同时还需要维护一个当前 dp 的值，用于判断 当前这个点 要不要新开一个新的组。

Code

const int N = 8100, mod = 1e9 + 7, INF = 1e10;
int lowbit(int x) { return x & -x; }
int gcd(int a, int b) { return a % b == 0 ? b : gcd(b, a % b); }

int a[N];
int d[N][2];//滚动数组。
int pre[N], mn[N];
// pre 代表当前的Dp值， mn代表 j-1中的 dp 的最小值

int stk[N];// 栈

//  走到 i 号点了 分了j 组的最小代价
void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) d[i][1] = max(d[i - 1][1], a[i]);
  //当前分成了 1组
  cout << d[n][1] << endl;
  for (int i = 2; i <= n; i++) {
    int tt = 0;
    pre[0] = INF;
    for (int j = i; j <= n; j++) {
      int temp = d[j - 1][(i - 1) & 1];// 
       // temp 相当于 如果不考虑 前面已经分好的组，一开始就是 前 j-1 个分成了 i-1 组
     // 栈维护一个递增的序列保证，这一段区间的max 都是由 aj 主导
      while (tt > 0 && a[stk[tt]] <= a[j]) temp = min(temp, mn[tt--]);
        
      stk[++tt] = j;
      mn[tt] = temp;// 当前的最小值
      pre[tt] = min(pre[tt - 1], temp + a[j]);
        // 可能 不在这个点 分成一个新的组 代价和比较小
      // if (j == 2) cout << temp << " " << pre[tt] << endl;
      d[j][i & 1] = pre[tt];// 更新
    }
    cout << d[n][i & 1] << endl;
  }
}

signed main() {
  kd;
  int _;
  _ = 1;
  // cin>>_;
  while (_--) solve();
  return 0;
}