【Neerc2016】养猫
问题描述
ls是一个特别堕落的小朋友，对于n个连续的小时，他将要么睡觉要么打隔膜，一个小时内他不能既睡觉也打隔膜，因此一个小时内他只能选择睡觉或者打隔膜，当然他也必须选择睡觉或打隔膜，对于每一个小时，他选择睡觉或打隔膜的愉悦值是不同的，对于第i个小时，睡觉的愉悦值为$s_i$，打隔膜的愉悦值为$e_i$，同时又有一个奥妙重重的规定：对于任意一段连续的k小时，ls必须至少有$t_1$时间在睡觉，$t_2$时间在打隔膜。那么ls想让他获得的愉悦值尽量大，他该如何选择呢？
输入格式
第一行四个整数,$n,k(1<=k<=n<=1000),t_1,t_2(0<=t_1,t_2<=k;t_1+t_2<=k$),含义如上所述。
接下来一行n个整数，第i个整数$s_i(0<=s_i<=10^9)$表示睡觉的愉悦值。
接下来一行n个整数，第i个整数$e_i(0<=e_i<=10^9)$表示打隔膜的愉悦值。
输出格式
一行输出最大的愉悦值。
样例输入
10 4 1 2
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
样例输出
69
这题比较劲，首先我们假设每天都打隔膜，然后令$x_i$表示第$i$天是否睡觉，如果睡觉就会产生$s_i-e_i$的愉悦值
然后对于$k$的限制，我们可以列出方程。
$$
\begin{cases}
t_1\leq x_1+x_2+\cdots+x_k\leq k-t_2\\
t_1\leq x_2+x_3+\cdots+x_{k+1}\leq k-t_2\\
\quad\quad\quad\quad\quad\quad\quad\quad\vdots\\
t_1\leq x_{n-k+1}+x_{n-k+2}+\cdots+x_n\leq k-t_2
\end{cases}
$$
然后我们要求的是$\sum_{i=1}^{n}(s_i-e_i)x_i$，这里$0\leq x_i\leq 1$，那么这就是一个线性规划问题。
这里可以用费用流来解决非负整数上的线性规划问题，现将不等式转化成等式，设一些辅助元。
$$
\begin{cases}\
x_1+x_2+\cdots+x_k&=t_1+y_1\\
x_1+x_2+\cdots+x_k&=k-t_2-z_1\\
x_2+x_3+\cdots+x_{k+1}&=t_1+y_2\\
&\vdots
\end{cases}
$$
然后在末尾添加一个方程$0=0$，然后对这个方程组差分，得到
$$
\begin{cases}\
x_1+x_2+\cdots+x_k&=t_1+y_1\\
y_1+z_1&=k-t_1-t_2\\
x_{k+1}+k-t_1-t_2&=x_1+y_2+z_1\\
&\vdots\\
k-t_2-z_{n-k+1}&=x_{n-k+1}+x_{n-k+2}+\cdots+x_n
\end{cases}
$$
然后观察这个方程组，我们可以发现，每一个变量恰好在等号左边和右边各出现了一次，又因为每个变量都是非负的，因此我们可以将每个变量看成边，变量的取值看成流量，每个等式看成一个点，然后这个方程就描述了每个点的出入流量守恒，因此我们可以假设左边为流出，右边为流入。
那么对于每个$x_i$，从他在左边的方程连到他在右边的方程，容量为$1$，费用为$s_i-e_i$
对于每个$y_i,z_i$，同样连接他所在的两个方程，容量为$inf$，费用为$0$
最后对于常数项，如果在左边，就从方程连到汇点，反之从源点连到方程，容量为它的值，费用为$0$
这样建好图之后，跑一遍最大费用最大流，再加上$\sum_{i=1}^{n}e_i$就是答案，正确性自己画个图感受一下就能明白。
代码：
1 |
|