链接
https://codeforces.com/problemset/problem/1856/C
题目
思路
卡了好久的题目，昨晚突然就做出来了。整体思路就是dp＋二分。我们知道这个序列长度的最大值是对任意i∈[1,n]，取a[i]+i-1的最大值；最小值就是max(a[i])(i∈[1,n])。
然后再遍历每个点判断是否有一个点能到达那个高度。利用dfs计算达到当前目标高度的步数，然后递归，并且如果最后一个的高度小于需要的高度，直接返回k+1步，让judge返回false即可。
代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
#define IOS ios::sync_with_stdio(false), cin.tie(0) ,cout.tie(0)
using namespace std;
#define int long long
const int N = 1e3 + 10;
int a[N];
int n, k;
bool fa = true;
int count(int id, int height)
{
if (id == n and height > a[id])return k + 1;
if (height > a[id])
return height - a[id] + count(id + 1, height - 1);
else return 0;
}
bool jd(int x)
{
for (int i = 1; i <= n; i++)
{
if (count(i, x) <= k and fa)return true;
}
return false;
}
signed main()
{
IOS;
int t; cin >> t;
while (t--)
{
cin >> n >> k;
int minn = 0, maxn = 0;
for (int i = 1; i <= n; i++) { cin >> a[i]; minn = max(a[i], minn); maxn = max(maxn, a[i] + i - 1); };
int l = minn, r = maxn;
while (l < r)
{
int m = (l + r + 1) / 2;
if (jd(m))l = m;
else r = m - 1;
}
cout << l << '\n';
}
return 0;
}