题解：CF727F Polycarp's problems
lkjzyd20
·
·
题解
题意
给定一个长为 n 的数列 a。m 次询问，每次给出 a_0 的值，求至少删去多少个数使任意位置的前缀和不为负数。
思路
设 f_{i,j}表示前 i 个数，保留 j 个数后的最大数。
则可得
f_{i,j} = \min(f_{i + 1,j}, \max(0,f_{i+1,j-1}-a_i))
+ 选择第 $i$ 个数不取，则
$$f_{i,j} = f_{i+1,j}$$
+ 选择第 $i$ 个数取，则
$$f_{i,j} = f_{i+1,j-1}-a_i$$
但我们还得要让前缀和不为负数，所以要对 $0$ 取 $\max$。
最后，我们再倒序枚举 $f_{1,x}$， 然后输出 $n-i$ 即可。
### 代码如下
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
const int N = 200010, M = 2010;
int a[N];
int f[M][M];
int n, m, x;
main()
{
scanf("%lld%lld", &n, &m);
rep(i, 1, n) scanf("%lld", &a[i]);
memset(f, 0x3f, sizeof f);
f[n + 1][0] = 0;
per(i, n, 1)
{
rep(j, 1, n - i + 1)
f[i][j] = min(f[i + 1][j], max(0ll, f[i + 1][j - 1] - a[i]));
f[i][0] = 0;
}
for(; m; -- m)
{
scanf("%lld", &x);
per(j, n, 0)
if(f[1][j] <= x)
{
printf("%lld\n", n - j);
break;
}
}
}
```