【题解】CF1348E：Phoenix and Berries

原题传送门
首先要发现一个性质
令 $suma=\sum_{i=1}^na_i,sumb同理$
答案的上界 $=[\frac{(suma+sumb)}{k}]$
下界 $=[\frac{suma}{k}]+[\frac{sumb}{k}]$
上界 $<=$下界+1，即要么上界=下界，要么上界=下界+1
证明略，发现这个上界的这个策略可能是达不到的，下界的这个方法是一定可以达到的，所以当上界=下界的时候，直接输出。但是如果上界=下界+1，那么因为下界的策略是取同一类型的，就考虑是否可以通过同一棵树上取一些东西使得取到上界的值

令 $suma$% $k=ra,sumb$% $k=rb$
若存在通过同一棵树上取下来这种策略的总数 $(xa,xb)$，就是 $a$取了 $xa$个， $b$取了 $xb$个，并且满足 $xa$% $k<=ra,xb$% $k<=rb$，那么就能取到上界
把上述条件转化， $xb$% $k=k-(xa$% $k)<=rb$，所以只要存在一个 $xa$使得 $xa$% $k$属于 $[k-rb,ra]$就行了
这个可以用 $dp_{i}$表示当前是否存在一个 $xa,xa$% $k=i$，用01背包可以求出来
只要存在一个这样的 $i$属于 $[k-rb,ra]$就能达到上界

接下来证明
$[\frac{suma}{k}]=m0,[\frac{sumb}{k}]=n0$
$[\frac{xa}{k}]=m,[\frac{xb}{k}]=n$
$[\frac{suma-xa}{k}]=m0-m,[\frac{sumb-xb}{k}]=n0-n$
$[\frac{xa+xb}{k}]=\frac{xa+xb}{k}=m+n+1$
成立

Code：

#include <bits/stdc++.h>
#define maxn 1010
#define LL long long
using namespace std;
int a[maxn], b[maxn], dp[maxn], n, k;
LL suma, sumb;inline int read(){int s = 0, w = 1;char c = getchar();for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);return s * w;
}int main(){n = read(), k = read();for (int i = 1; i <= n; ++i) suma += a[i] = read(), sumb += b[i] = read();if ((suma + sumb) / k == (suma / k + sumb / k)) return printf("%lld\n", (suma + sumb) / k), 0;LL r = suma % k, l = k - sumb % k;dp[0] = 1;for (int t = 1; t <= n; ++t){for (int i = k - 1; i >= 0; --i)if (dp[i]) for (int j = 1; j < k; ++j)if (j <= a[t] && k - j <= b[t]) dp[(i + j) % k] = 1;for (int i = l; i <= r; ++i) if (dp[i]) return printf("%lld\n", (suma + sumb) / k), 0;}printf("%lld\n", suma / k + sumb / k);return 0;
}