承前省略优化¶

没错这个优化并不是一个被承认的优化，它更加偏向是一种dp的技巧，被广泛运用在背包中。但是有些题目也使用了这个优化，因此单独拿出来讲。

例题 #1 游戏¶

题目描述

给定两个正整数数列，你要用它们来做一个游戏：你需要对数列进行若干次操作，每一次操作，应选择两个正整数 \(k_1\) 和 \(k_2\)，并删除第一个数列的最后 \(k_1\) 个数，计算出它们的和 \(s_1\)；删除第二个数列的最后 \(k_2\) 个数，计算出它们的和 \(s_2\)。这一次操作的得分就是 \((s_2-k_2)\times(s_1-k_1)\)。两个数列应同时被清空，不允许一个数列空了，而另一个数列中还有数。游戏的总得分就是每一次操作的得分总和。

求最小的总得分。

输入格式

第一行是两个整数 \(n\) 和 \(m\)，分别表示第一个数列和第二个数列的初始长度。

第二行有 \(n\) 个正整数，是第一个数列的数。

第三行有 \(m\) 个正整数，是第二个数列的数。

数列中的数都不超过 \(1000\)。

输出格式

一个整数，表示最小的总得分。

对于 \(100\%\) 的数据，\(n,m\le2000\)。

首先将每个数-1，可以去掉代价式中的k。然后我们考虑做法。

很明显是二维dp，状态很好定义，d_{i,j}为使用了a中后i个数和b中后j个数字时的最小代价。为了方便转移我们转化为插入了a中前i个和b中后i个时的代价。

很容易写出O(n^4)的dp，那么怎么优化呢？

如果是一维的情况，我们也许会考虑拆分贡献，维护前缀max。但是二维我们不可以这样做。

发现如果从a,b中各自取出>1个数，那么其贡献根据乘法分配律，大于a每次取1个数，我们又要代价最小。因此得出结论：每次最多注意偶一边取>1个数。

这样也很难写。考虑a数列删去\(a_{i} \(的时候b数列同时删去\)b_{j} \(和之前连续的一段数（\)b_{j-1} \(、\)b_{j-2} \(……、\)b_{k} \(），那么就是\)p[i-1][k-1]+a_{i}\times\sum_{x=k}^{j-1} b_{x}\),由于\(a_{i}\times\sum_{x=k}^{j-1} b_{x}\)已经更新过\(p[i][j-1]\)，所以也即是\(p[i][j-1]+a[i]\times b[j]\)。这样就利用了承前的信息来优化了。

// Problem: P1846 游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1846
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
// 
#include<bits/stdc++.h>

using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long 
#define pb push_back
#define itn int
#define ps second 
#define pf first


#define rd read()
int read()
{
  int xx = 0, ff = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9')
  {
    if (ch == '-')
      ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    xx = xx * 10 + (ch - '0'), ch = getchar();
  return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
    cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
    for (auto v: a) cerr << v << ' ';
    err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
    cerr << a << ' ';
    err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e3+5;
const ull P=137;
const int INF=1e18+7;
/*

策略


*/  


int a[N],b[N];
int f[N][N];


signed main(){
    int n=rd,m=rd;
    for(int i=1;i<=n;i++){
        a[i]=rd-1;
    }

    for(int i=1;i<=m;i++){
        b[i]=rd-1;
    }

    memset(f,0x3f3f,sizeof f);
    f[0][0]=0;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=min(f[i][j],f[i-1][j-1]+a[i]*b[j]);
            f[i][j]=min(f[i][j],f[i][j-1]+a[i]*b[j]);
            f[i][j]=min(f[i][j],f[i-1][j]+a[i]*b[j]);
        }
    }

    cout<<f[n][m]<<endl;
}

例题 #2 [NOIP2014 提高组] 飞扬的小鸟¶

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编:

游戏界面是一个长为 \(n\)，高为 \(m\) 的二维平面，其中有 \(k\) 个管道（忽略管道的宽度）。

小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为 \(1\)，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 \(x\)，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 \(y\)。小鸟位于横坐标方向不同位置时，上升的高度 \(x\) 和下降的高度 \(y\) 可能互不相同。

小鸟高度等于 \(0\) 或者小鸟碰到管道时，游戏失败。小鸟高度为 \(m\) 时，无法再上升。

现在,请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

输入格式

第 \(1\) 行有 \(3\) 个整数 \(n, m, k\)，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开；

接下来的 \(n\) 行，每行 \(2\) 个用一个空格隔开的整数 \(x\) 和 \(y\)，依次表示在横坐标位置 \(0 \sim n-1\) 上玩家点击屏幕后，小鸟在下一位置上升的高度 \(x\)，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度 \(y\)。

接下来 \(k\) 行，每行 \(3\) 个整数 \(p,l,h\)，每两个整数之间用一个空格隔开。每行表示一个管道，其中 \(p\) 表示管道的横坐标，\(l\) 表示此管道缝隙的下边沿高度，\(h\) 表示管道缝隙上边沿的高度（输入数据保证 \(p\) 各不相同，但不保证按照大小顺序给出）。

输出格式

共两行。

第一行，包含一个整数，如果可以成功完成游戏，则输出 \(1\)，否则输出 \(0\)。

第二行，包含一个整数，如果第一行为 \(1\)，则输出成功完成游戏需要最少点击屏幕数，否则，输出小鸟最多可以通过多少个管道缝隙。

对于 \(100\%\) 的数据：\(5 \leq n \leq 10000\)，\(5 \leq m \leq 1000\)，\(0 \leq k < n\)，\(0 < x,y < m\)，\(0 < p < n\)，\(0 \leq l < h \leq m\)， \(l + 1 < h\)。