- 1#include 2#include 3#include 4#define maxn 50010 5 //用f[i]表示在做第i道题的情况下,前i道题在合法状况下
- 6 //(即空题段长度不超过mid)可能的所有方案中的最小时间
- 7 // 得到状态转移方程f[i]=min(f[j]+a[i],f[i])
- 8 using namespace std;
- 9 int a[maxn],
- n,
- t,
- f[maxn];
- 10 bool Judge(int x) {
- 11 memset(f, 0x3f, sizeof(f));
- 12 f[0] = 0;
- 13
- for (int i = 1; i <= n; i++) {
- 14
- for (int j = max(i - x - 1, 0); j) {
- 15 f[i] = min(f[i], f[j] + a[i]);
- 16
- }
- 17
- }
- 18 int rt = 0x7f;
- 19
- for (int i = n - x - 1; i <= n; i++) rt = min(rt, f[i]);
- 20
- if (rt <= t) return true;
- 21
- else return false;
- 22
- }
- 23 int main() 24 {
- 25 scanf("%d%d", &n, &t);
- 26
- for (int i = 1; i <= n; i++) 27 scanf("%d", &a[i]);
- 28 int l = 0,
- r = n,
- ans = n;
- 29
- while (l < r) {
- 30 int mid = (l + r) / 2;
- 31
- if (Judge(mid)) r = mid;
- 32
- else l = mid + 1;
- 33
- }
- 34 printf("%d", l + 1);
- 35
- return 0;
- 36
- }
来源: http://www.bubuko.com/infodetail-1949092.html