题目链接：BZOJ - 1221
题目分析
算法一：最小费用最大流
首先这是一道经典的网络流问题。每天建立两个节点，一个 i 表示使用毛巾，一个 i' 表示这天用过的毛巾。
然后 i 向 T 连 Ai （第 i 天需要的毛巾数）。从 S 向 i' 连 Ai ，这样这天新增的用过的毛巾就是 Ai 了。
然后 i' 可以连向 (i+1)' ，表示留到下一天再处理，i' 还可以流向 i+p+1 和 i+q+1，表示洗了之后再次使用，这两种边是有费用的。
还有就是新购买毛巾，从 S 向 i 连，费用就是买新毛巾的费用。
这样，使用最小费用最大流就可以解决这道题了。
算法二：三分
然而这道题目有一个神奇的做法，速度远远快于费用流的解法。
我发现提交记录里 faebdc 神犇的代码速度极其快，于是我就向他请教，他告诉我这道题是集训队作业里的一道..那道题目的数据范围是 n <= 10^5 ... 我只能Orzzz。
在 faebdc 神犇的光辉照耀下，我终于似懂非懂写出了这个三分的代码..
首先，如果已经确定要购买多少毛巾，一定一开始就先购买这些毛巾是最优的。然后之后的每天一定先使用没用过的，再使用花费少的洗涤方式，再使用花费多的洗涤方式。
这样，使用一个队列就可以 O(n) 计算出购买 x 条毛巾时的最少花费了，记为 f(x) 。
然后..重点是.. 可以分析出 f(x) 是一个单谷的函数，可以三分 x 。（怎么分析出的呢= = faebdc 神犇讲解了一下然后我太弱听不懂...
然后就可以愉快地三分了..
代码
费用流代码：
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue> using namespace std; const int MaxN = 1000 + 5, INF = 999999999; inline int gmin(int a, int b) {return a < b ? a : b;}
inline int gmax(int a, int b) {return a > b ? a : b;} int n, p, q, f, fp, fq, S, T, Tot, MinCost, MaxFlow;
int d[MaxN * 2]; bool InQue[MaxN * 2]; struct Edge
{
int u, v, w, Ct;
Edge *Next, *Other;
} E[MaxN * 12], *P = E, *Point[MaxN * 2], *Pre[MaxN * 2]; inline void AddEdge(int x, int y, int z, int k)
{
Edge *Q = ++P; ++P;
P -> u = x; P -> v = y; P -> w = z; P -> Ct = k;
P -> Next = Point[x]; Point[x] = P; P -> Other = Q;
Q -> u = y; Q -> v = x; Q -> w = 0; Q -> Ct = -k;
Q -> Next = Point[y]; Point[y] = Q; Q -> Other = P;
} queue<int> Q; bool Found()
{
memset(d, 0x7f, sizeof(d));
memset(InQue, 0, sizeof(InQue));
while (!Q.empty()) Q.pop();
d[S] = 0; InQue[S] = true; Q.push(S);
int x;
while (!Q.empty())
{
x = Q.front(); InQue[x] = false; Q.pop();
for (Edge *j = Point[x]; j; j = j -> Next)
if (j -> w && d[x] + j -> Ct < d[j -> v])
{
d[j -> v] = d[x] + j -> Ct;
Pre[j -> v] = j;
if (!InQue[j -> v])
{
InQue[j -> v] = true;
Q.push(j -> v);
}
}
}
return d[T] < INF;
} void Augment()
{
int Flow = INF;
for (Edge *j = Pre[T]; j; j = Pre[j -> u]) Flow = gmin(Flow, j -> w);
for (Edge *j = Pre[T]; j; j = Pre[j -> u])
{
j -> w -= Flow;
j -> Other -> w += Flow;
}
MaxFlow += Flow;
MinCost += Flow * d[T];
} int main()
{
scanf("%d%d%d%d%d%d", &n, &p, &q, &f, &fp, &fq);
int Num;
Tot = n * 2; S = ++Tot; T = ++Tot;
for (int i = 1; i <= n; ++i)
{
scanf("%d", &Num);
AddEdge(S, i, Num, f);
AddEdge(i, T, Num, 0);
AddEdge(S, n + i, Num, 0);
}
for (int i = 1; i < n; ++i)
{
AddEdge(n + i, n + i + 1, INF, 0);
if (i + p + 1 <= n) AddEdge(n + i, i + p + 1, INF, fp);
if (i + q + 1 <= n) AddEdge(n + i, i + q + 1, INF, fq);
}
while (Found()) Augment();
printf("%d\n", MinCost);
return 0;
}
三分代码：
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm> using namespace std; inline void Read(int &Num)
{
char c = getchar();
while (c < '0' || c > '9') c = getchar();
Num = c - '0'; c = getchar();
while (c >= '0' && c <= '9')
{
Num = Num * 10 + c - '0';
c = getchar();
}
} const int MaxN = 1000 + 5, INF = 999999999; inline int gmin(int a, int b) {return a < b ? a : b;} int n, p, q, f, fp, fq, SumA, Head, Tail;
int A[MaxN], Q[MaxN][2], Ans; int Calc(int x)
{
int ret, Cnt, Rest;
Head = 1; Tail = 0;
Rest = x;
ret = 0;
for (int i = 1; i <= n; ++i)
{
if (i - p - 1 > 0)
{
Q[++Tail][0] = i - p - 1;
Q[Tail][1] = A[i - p - 1];
}
if (Rest >= A[i]) Rest -= A[i];
else
{
Cnt = A[i] - Rest;
Rest = 0;
while (Cnt > 0 && Head <= Tail)
{
if (Q[Head][0] <= i - q - 1)
{
if (Q[Head][1] > Cnt)
{
ret += Cnt * fq;
Q[Head][1] -= Cnt;
Cnt = 0;
}
else
{
ret += Q[Head][1] * fq;
Cnt -= Q[Head][1];
++Head;
}
}
else
{
if (Q[Tail][1] > Cnt)
{
ret += Cnt * fp;
Q[Tail][1] -= Cnt;
Cnt = 0;
}
else
{
ret += Q[Tail][1] * fp;
Cnt -= Q[Tail][1];
--Tail;
}
}
}
if (Cnt > 0) return INF;
}
}
ret += f * x;
return ret;
} int main()
{
scanf("%d%d%d%d%d%d", &n, &p, &q, &f, &fp, &fq);
for (int i = 1; i <= n; ++i)
{
Read(A[i]);
SumA += A[i];
}
int l = 1, r = SumA, mid1, mid2;
while (r - l >= 3)
{
mid1 = l + (r - l) / 3;
mid2 = r - (r - l) / 3;
if (Calc(mid1) < Calc(mid2)) r = mid2 - 1;
else l = mid1 + 1;
}
Ans = INF;
for (int i = l; i <= r; ++i) Ans = gmin(Ans, Calc(i));
printf("%d\n", Ans);
return 0;
}