LOJ500 ZQC的拼图 二分答案、DP

传送门

题意：给出$N$个直角三角形拼图和$M \times M$的网格，第$i$个直角三角形水平直角边边长为$\frac{1}{a_i}$，垂直直角边边长为$\frac{1}{b_i}，$规定直角三角形只能直角顶点在右上方地摆放，直角顶点必须摆放在网格的顶点处，且水平直角边和垂直直角边必须与网格的某一条线重合，三角形可以越出网格。现在你可以将每个三角形都放大正整数$K$倍，求存在一种摆放方案使得存在一条只经过直角三角形覆盖区域的$(0,0)$到$(M,M)$的路径的$K$的最小值。$N , M \leq 100 , a_i , b_i \leq 10^6$

---

显然是有二分性质的

首先考虑到交换两个直角三角形对答案实际上没有影响，所以拼图的顺序是无所谓的。

所以我们选择DP作为二分的check。设$f_{i,j}$表示前$i$个拼图在横坐标为$j$时最大的纵坐标大小，转移方程用枚举当前三角形直角顶点的位置加上相似推一下就行。

 #include<bits/stdc++.h>

 #define LOJ

 //This code is written by Itst

 #define ll long long

 using namespace std;

 inline int read(){

     int a = ;

     bool f = ;

     char c = getchar();

     while(c != EOF && !isdigit(c)){

         if(c == '-')

             f = ;

         c = getchar();

     }

     while(c != EOF && isdigit(c)){

         a = (a << ) + (a << ) + (c ^ '');

         c = getchar();

     }

     return f ? -a : a;

 }

 ll tri[][] , dp[] , N , M;

 bool check(int mid){

     memset(dp , -0x3f , sizeof(dp));

     dp[] = ;

     for(int i =  ; i <= N ; i++)

         for(int j = M ; j >=  ; j--)

             for(int k = j ; k >=  && (j - k) * tri[i][] <= mid ; k--)

                 dp[j] = max(dp[j] , dp[k] + (mid - (j - k) * tri[i][]) / tri[i][]);

     return dp[M] >= M;

 }

 int main(){

 #ifdef LOJ

     freopen("500.in" , "r" , stdin);

     //freopen("500.out" , "w" , stdout);

 #endif

     N = read();

     M = read();

     for(int i =  ; i <= N ; i++){

         tri[i][] = read();

         tri[i][] = read();

     }

     int L =  , R = 1e8;

     while(L < R){

         int mid = L + R >> ;

         check(mid) ? R = mid : L = mid + ;

     }

     cout << L;

     return ;

 }