有N个数(N<=100000) ，在连续M（M<=N）个数里至少要有一个数被选择. 求选出来数的最小总和。
输入
第一行两个整数 N，M 接下来N行 Wi（Wi<=100） 表示第i个数
输出
一个整数，最小总和
样例
输入
5 3
1
2
5
6
2
输出
4
提示
2+2=4
Sol:
定义f[i]为一定选择第i个数字，且保证前i个数字都满足题意的最小代价
则可以写出这样的方程f[i]:=min{f[j]}+a[i]（i-m<=j<=i-1）
（因为要保证从i向左数的m个数字均要被覆盖）
于是对于样例
输入数字 1 2 5 6 3 4 1
f数组 1 2 5 7 5 9 6
则对于6来说， f[4]=min(1,2,5)+6=7
则对于3来说， f[5]=min(2,5,7)+3=5
则对于4来说， f[6]=min(5,7,5)+4=9
则对于1来说， f[4]=min(7,5,9)+1=6
由于覆盖第n个数字，我们可以选择f[n-m+1]...f[n]中的最小值
于是扫一遍就好了。
暴力程序如下:
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, q[N], h = 1, t, num[N], a[N << 1], ans, f[N << 1];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= m; ++i)
f[i] = a[i];
for (int i = m + 1; i <= n; i++)
{
for (int j = i - m; j < i; j++)
//要从[i-m,i-1]这段中选个最小的f[j]+a[i]出来
f[i] = min(a[i] + f[j], f[i]);
}
ans = 0x3f3f3f3f;
for (int i = n - m + 1; i <= n; i++)
//如果要覆盖第n个city,则从[n-m+1,n]中选择
ans = min(ans, f[i]);
printf("%d", ans);
return 0;
}
发现此题关键是在某个大小固定的区间求一个极小值，于是可以单调队列之
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline int read();
const int N = 2e5 + 1;
int n, m, h, t;
int a[N], q[N];
int f[N];
void work()
{
h = 0;
t=0;//注意h的初值为0
f[0]=0;
for (int i = 1; i <= n; i++)
{
while (q[h] < i - m && h <= t)
h++;
f[i] = f[q[h]] + a[i];
//单调上升队列,取[i-m,i-1]这个区间中值最小的f值
while (f[i] <= f[q[t]] && h <= t) t--;
q[++t] = i; //维护一个单调上升的f值组成的数列,注意不是a值
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
work();
int ans = 1e9;
for (int i = n - m + 1; i <= n; i++)
ans = min(ans, f[i]);
printf("%d", ans);
return 0;
}
绿色通道
高二数学《绿色通道》总共有N道题目要抄，编号1..N，抄第i 题要花ai分钟。小 Y 决定只用不超过t 分钟抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。现在，小 Y想知道他在这t分钟内写哪些题，才能够尽量减轻马老师的怒火。由于小 Y 很聪明，你只要告诉他最长的空题段至少有多长就可以了，不需输出方案。
输入
第一行为两个整数n,t 。 第二行为n个整数，依次为a1....an 。
0<N<=50000 0<ai<=3000 0<t<10^8
输出
输出一个整数，表示最长的空题段至少有多长。
样例
输入
17 11
6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5
输出
3
Sol:同上一题，二分枚举下答案即可
/*
设k为最长的空题数
问题转换为每k+1个数字至少要取一个数，
取出的数字之和小于等于t
二分枚举k即可
*/
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 5e4 + 50;
const int inf = 0x3f3f3f3f;
int n, t, l, r, mid, ans;
int a[N], q[N], f[N];
int head, tail;
bool check(int mid)
{
memset(f, 0, sizeof(f));
memset(q, 0, sizeof(q));
head = tail = 1;
for (int i = 1; i <= n; i++)
{
while (head <= tail && q[head] < i - mid - 1)
head++;
f[i] = f[q[head]] + a[i];
while (head <= tail && f[i] <= f[q[tail]])
tail--;
q[++tail] = i;
}
int ans = inf;
for (int i = n; i >= n - mid; i--)
{
if (f[i] <= t)
return 1;
}
return 0;
}
int main() {
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int l = 1, r = n;
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid))
r = mid - 1;
else
l = mid + 1;
}
printf("%d
", r + 1);
return 0;
}