of baskets he can fill completely!Help Phoenix determine the maximum number

Problem Description Phoenix is picking berries in his backyard. There are n shrubs, and each shrub has ai red berries and bi blue berries.

Each basket can contain k berries. But, Phoenix has decided that each basket may only contain berries from the same shrub or berries of the same color (red or blue). In other words, all berries in a basket must be from the same shrub or/and have the same color.

For example, if there are two shrubs with 5 red and 2 blue berries in the first shrub and 2 red and 1 blue berries in the second shrub then Phoenix can fill 2 baskets of capacity 4 completely:

the first basket will contain 3 red and 1 blue berries from the first shrub; the second basket will contain the 2 remaining red berries from the first shrub and 2 red berries from the second shrub. Help Phoenix determine the maximum number of baskets he can fill completely!

Input The first line contains two integers n and k (1≤n,k≤5001≤n,k≤5001≤n,k≤500) — the number of shrubs and the basket capacity, respectively.

The i-th of the next n lines contain two integers aia_ia i ​ and bib_ib i ​ (0≤ai,bi≤1090≤a_i,b_i≤10^90≤a i ​ ,b i ​ ≤10 9 ) — the number of red and blue berries in the i-th shrub, respectively.

Output Output one integer — the maximum number of baskets that Phoenix can fill completely.

Sample Input 2 4 5 2 2 1

Sample Output 2

题意 n棵树，每棵树上有ai个红果实和bi个蓝果实。有可以装k个果实的篮子，一个篮子只能放同种颜色或同一棵树上的果实。求最多可以放满多少个篮子？

题解 显然大多数篮子内的果实都是同颜色的，最多只有n个篮子内的果实是不同色的(若同棵树有多个篮子装的不同色果实，可以将其转为为多个同色篮和一个不同色)。所以只需要考虑每棵树不同颜色的那个篮子的组成。 设dp[i][j]dp[i][j]dp[i][j]为考虑第iii棵树果实装完后剩下的红果实数量为jjj能装满的最大篮子数。 (蓝果实呢？设dp[i][j][z]dp[i][j][z]dp[i][j][z]，zzz代表剩余蓝果实的话，复杂度为5004500^4500 4 ，显然会超时，实际上一个jjj对应的剩余蓝果实数量是唯一的，等于 果实总数−dp[i][j]∗k−j果实总数-dp[i][j]*k-j果实总数−dp[i][j]∗k−j)。

状态转移：设第iii棵树之前的红蓝果实总数为sumsumsum； 枚举不同颜色的那个篮子的组成，由s1s1s1个红果实和k−s1k-s1k−s1个蓝果实组成。 则考虑之前的剩余果实，剩余未装篮的红果实有num1=j+a[i]−s1num1 = j+a[i]-s1num1=j+a[i]−s1个，未装篮的蓝果实数量为num2=b[i]−(k−s1)+sum−dp[i][j]∗k−jnum2 = b[i]-(k-s1)+sum-dp[i][j]*k-jnum2=b[i]−(k−s1)+sum−dp[i][j]∗k−j。

所以递推式为 dp[i+1][num1%k]=max(dp[i+1][num1%k],dp[i][j]+1+num1/k+num2/k)dp[i+1][num1%k] = max(dp[i+1][num1%k], dp[i][j]+1+num1/k+num2/k) dp[i+1][num1%k]=max(dp[i+1][num1%k],dp[i][j]+1+num1/k+num2/k)

然后考虑不存在不同色篮的转移的情况即可。

取dp[i][j]最大值即为所求。

#include<stdio.h>
 #include
 #include
 #include
 #include
 #include
 #include
 #include
 #include
 #include
 #define dbg(x) cout<<#x<<" = "<<x<<endl;
 #define INF 0x3f3f3f3f
 #define eps 1e-6
using namespace std;
 typedef long long LL;
 typedef pair<int, int> P;
 const int maxn = 520;
 const int mod = 1000000007;
 LL dp[maxn][maxn];
 int a[maxn], b[maxn];
int main()
 {
 int n, k, i, j, k2, s1;
 LL sum = 0, mx = 0;
 memset(dp, -1, sizeof(dp));
 scanf("%d %d", &n, &k);
 k2 = 2*k;
 for(i=0;i<n;i++)
 scanf("%d %d", &a[i], &b[i]);
 dp[0][0] = 0;
 for(i=0;i<n;i++)
 {
 for(j=0;j<k;j++)
 if(dp[i][j]>=0){
 int b1 = sum-dp[i][j]*k-j;
 for(s1=1;s1<=a[i] && s1<k;s1++)
 if(b[i]+s1>=k)
 {
 int b2 = b1+b[i]-(k-s1);
 int a2 = j+a[i]-s1;
 dp[i+1][a2%k] = max(dp[i+1][a2%k], dp[i][j]+b2/k+a2/k+1);
 }
 dp[i+1][(j+a[i])%k] = max(dp[i+1][(j+a[i])%k], dp[i][j]+(j+a[i])/k+(b1+b[i])/k);
 }
 sum += a[i]+b[i];
 }
 for(i=0;i<=n;i++)
 for(j=0;j<=k;j++)
 mx = max(dp[i][j], mx);
 printf("%I64d\n", mx);
 return 0;
 }