Description：

有一个升序数组和一个没有在这个数组中出现过的数，给出和每个元素比较大小的花费，确定一种方案使得无论这个数是多少，最大花费最小。

$1\leqslant n\leqslant 10^5,1\leqslant cost_i\leqslant 9$

Solution：

首先有一个简单的 $O(n^3)$ 的区间 $DP$ ，就是 $f[i][j]=\min(\max(f[i][k-1],f[k+1][j])+a[k])$ ，但是这个不是很好优化，发现答案一定不会超过 $9\log n$ ，那么就可以利用那个把要求解的答案放到状态里的做法，设 $f[c][x]$ 表示花费 $c$ 的代价左端点为 $x$ 时右端点最远到哪里，那么显然 $f[c][x]$ 关于 $x$ 和 $c$ 都是单调的，那么转移方程为 $f[c][x]=\max(f[c-a_i][i+1](i\leqslant f[c-a_i][x]+1))$ ，但是这样转移还是 $O(n^2)$ 的，于是我们可以枚举 $a_i$ ，那么对于 $a_i$ 相同的由上面的单调性我们一定选最靠后的，那么我们可以预处理 $p[x][i]$ 表示在 $i$ 及之前最靠后的一个 $x$ 的位置，然后按上面那个转移就行了，时间复杂度 $O(n\log n\times 81)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int a[MAXN];

int f[180][MAXN];

int p[10][MAXN];

int main()

{

	freopen("cost.in","r",stdin);

	freopen("cost.out","w",stdout);

	char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		a[++n] = c - '0';

		c = getchar();

	}

	for(int i = 1;i <= n;++i)p[a[i]][i] = i;

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= 9;++j)p[j][i] = (p[j][i] == 0 ? p[j][i - 1] : i);

	for(int i = 1;i <= n;++i)

	{

		f[a[i]][i] = i;

		for(int j = 1;j < a[i];++j)f[j][i] = i - 1;

	}

	for(int k = 1;k < 180;++k)

	{

		for(int i = 1;i <= n;++i)

		{//cout << k << " " << i << " : " << endl;

			for(int j = 1;j <= min(9,k);++j)

			{

				int pos = p[j][min(n,f[k - j][i] + 1)];//cout << pos << endl;

				if(pos == 0)continue;

				if(pos == n)f[k][i] = n;

				else f[k][i] = max(f[k][i],f[k - j][pos + 1]);

			}//cout << k << " " << i << " " << f[k][i] << endl;

		}

		if(f[k][1] >= n)

		{

			cout << k << endl;

			break;

		}

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}