首先考虑只按颜色分配的当前答案ans，那么最后剩下的果子数在[0,2k-2]之间，如果剩下的果子数在[0,k-1]之间，那么当前的ans就是最终答案，如果剩下的果子数在[k,2k-2]之间，那么最多答案还可以加一，也就是答案有可能是ans+1，下面我们用dp判断有无这种可能性
举个例子：
n=1 k=5
a1=4 b1=3
那么可以放弃一对(5,5)，而选择(4,1)、(3,2)或(2,3)，最后再用剩下的（这次剩下的和之前剩下的）填上这个(5,5)，那么答案就增加了1
但是直接这样写时间复杂度太高了，和a[i]、b[i]相关
可以考虑每次填上一对(5,5)时直接把它拿出来，也就是对k取模即可
时空复杂度都是O(n^3)
（写到这里已经可以过这道题了，下面考虑进一步优化：）
空间上可以考虑i+j==k，滚动数组分别优化掉一维，空间复杂度O(n)
时间上可以考虑bitset优化，时间复杂度O(n^3/32)
下面的代码是无优化的：
（一个想法：可能可以用网络流实现，大噶有会的可以在评论里回复我或者Q我，谢谢大噶~）
#include<bits/stdc++.h>
using namespace std;
#define LL long long
bool f[505][505][505];
int n, i, g[505][505], j, t;
LL suma, sumb, ans, p, k, a[505], b[505], ta, tb;
int main (void)
{
scanf("%d%lld",&n,&k);
for (i=1; i<=n; i++) {
scanf("%lld%lld",&a[i],&b[i]);
suma+=a[i];
sumb+=b[i];
}
ans=suma/k+sumb/k;
suma%=k,sumb%=k;
if (suma+sumb<k) {
printf("%lld\n",ans);
return 0;
}
for (i=1; i<=suma; i++)
if (k-i<=sumb) g[i][k-i]=1;
f[0][0][k]=f[0][k][0]=1;
for (i=1; i<=n; i++) {
for (j=0; j<=k; j++) f[i][j][k-j]=f[i-1][j][k-j];
for (j=1; j<k; j++) {
if (j<=a[i]&&k-j<=b[i]) {
ta=k-j,tb=k-(k-j);
for (t=0; t<=k; t++) {
f[i][(t+ta)%k][(k-t+tb)%k]|=f[i-1][t][k-t];
//printf("%d %d %d %d\n",(t+ta)%k,(k-t+tb)%k,t,k-t);
}
}
}
}
p=0;
for (i=1; i<=suma; i++)
if (k-i<=sumb&&g[i][k-i]&&f[n][k-i][i]) p=1LL;
ans+=p;
printf("%lld\n",ans);
return 0;
}
Codeforces Round #638 (Div. 2) E Phoenix and Berries
原文：https://www.cnblogs.com/chinakevin/p/12818886.html