【题目大意】
有$n$天，每天能吃饭、睡觉、什么事也不干
每天吃饭的愉悦值为$e_i$，睡觉的愉悦值为$s_i$，什么都不干愉悦值为0。
要求每连续$k$天都要有至少$E$天吃饭，$S$天睡觉。
求最大愉悦值。
$k leq n leq 1000, 0leq s_i, e_i leq 10^9, 0 leq E+S leq k$
【题解】
首先什么都不干这个是xjb写的肯定没有用。。
然后我们考虑费用流，我钦定n天都睡觉，那么假设有一天吃饭，那么我们换成吃饭的费用就是$e_i-s_i$。
两个限制只要考虑一个即可，因为另外一个一定满足了。
如果只有睡觉的限制，那么我们要满足的就是从$i$连到$i+1$的，容量不能超过$S$，在$i$连到$i+1$的边都表示这天我睡觉（因为已经钦定了），容量$S$，费用0。
那么吃饭没有限制，就可以从每个$i$连到$i+K$（不够的话到汇点），容量为1，费用为$e_i-s_i$。
然后我们就是求最大费用最大流。
考虑有了限制，相当于我从$i$到$i+1$的边容量变为$r-l$（上界-下界），就代表我一定要有吃饭的流量。
从$i$到$i+1$画一条纵截线，与其相交并且是$i$到$i+k$这样的边至少有$l$个。
我们再对源点容量做一下限制即可。
复杂度$O(costflow(n, 2n))$
upd: 我们把每个$k$天区间变换成$[i-k+1,i]$这样的末尾$i$表示，那么第$i$天选择吃饭，就会对于$[i, min(i+k-1, n)]$有贡献。
问题变成，选出若干区间，使得$(k, k+1, ..., n)$都被覆盖了$[E, k-S]$次。
显然这个图可以满流，那么最大流量就是$max_e$，也就是$k-S$，一定会流满。
那么我们限制了$i$到$i+1$的边流量为$[0, k-S-E]$，就相当于设置$i$到$i+k$的边的流量至少为$E$了。
这样就满足题目要求了
# include <queue> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int N = 1e5 + 10, M = 1e5 + 10; const ll inf = 1e17 + 10; int n, K, SS, EE; int s[M], e[M]; int S, T; int head[M], nxt[M], to[M], w[M], flow[M], tot = 1; inline void add(int u, int v, int fl, int _w) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; flow[tot] = fl, w[tot] = _w; } inline void adde(int u, int v, int fl, int _w) { add(u, v, fl, _w); add(v, u, 0, -_w); } namespace MCF { queue<int> q; int pre[M]; ll d[M]; bool vis[M]; inline bool spfa() { while(!q.empty()) q.pop(); for (int i=1; i<=T; ++i) vis[i] = 0, d[i] = inf; vis[S] = 1; d[S] = 0; q.push(S); while(!q.empty()) { int top = q.front(); q.pop(); vis[top] = 0; for (int i=head[top]; i; i=nxt[i]) { if(d[to[i]] > d[top] + w[i] && flow[i]) { d[to[i]] = d[top] + w[i]; pre[to[i]] = i; if(!vis[to[i]]) { vis[to[i]] = 1; q.push(to[i]); } } } } return d[T] < inf; } inline ll mcf() { int fl = 1e9; ll ret = 0; for (int i=pre[T]; i; i=pre[to[i^1]]) fl = min(fl, flow[i]); for (int i=pre[T]; i; i=pre[to[i^1]]) { flow[i] -= fl; flow[i^1] += fl; ret += 1ll * fl * w[i]; } return ret; } inline ll main() { ll ans = 0; while(spfa()) ans += mcf(); return ans; } } int main() { // freopen("delight.in", "r", stdin); // freopen("delight.out", "w", stdout); cin >> n >> K >> SS >> EE; ll sum = 0; for (int i=1; i<=n; ++i) { scanf("%d", &s[i]); sum += s[i]; } for (int i=1; i<=n; ++i) { scanf("%d", &e[i]); e[i] -= s[i]; } int mi = EE, mx = K - SS; int S0 = n+1; S = n+2; T = n+3; // [mi, mx] adde(S, S0, mx, 0); for (int i=1; i<=n; ++i) { if(i <= K) adde(S0, i, 1e9, 0); if(i+1 <= n) adde(i, i+1, mx-mi, 0); else adde(i, T, mx-mi, 0); if(i+K <= n) adde(i, i+K, 1, -e[i]); else adde(i, T, 1, -e[i]); } cout << sum - MCF::main() << endl; return 0; }