loj#500 「LibreOJ β Round」ZQC 的拼图

分析

二分倍数

然后考虑dp[i][j]表示选到第i个x轴覆盖到j的情况y轴最多覆盖多少

贡献柿子可以画图然后相似三角形得到

代码

#include<bits/stdc++.h>
using namespace std;
int a[110],b[110],n,m,dp[110][110];
inline bool ck(int mid){
    int i,j,k;
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0]=0;
    for(i=1;i<=n;i++)
      for(j=0;j<=m;j++)
        for(k=j;k>=0&&(j-k)*a[i]<=mid;k--)
          dp[i][j]=max(dp[i][j],dp[i-1][k]+(mid-(j-k)*a[i])/b[i]);
    return dp[n][m]>=m;
}
int main(){
    int i,j,k,le=0,ri=1e8;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
    while(ri-le>1){
      int mid=(le+ri)>>1;
      if(ck(mid))ri=mid;
        else le=mid;
    }
    printf("%d
",ri);
    return 0;
}