avatar

目录
Loj #500 ZQC 的拼图

题目相关

题目链接:#500 ZQC 的拼图

题目描述:

  ZQC 和他的妹子在玩拼图。她们有 $n(1≤n≤100)$ 块神奇的拼图,还有一块拼图板。拼图板是一个 $m\times m(1≤m≤100)$ 的正方形网格,每格边长为 1,如图所示。每块拼图都是直角三角形,正面为白色,反面为黑色,拼图放在拼图板上时,必须正面朝上,直角顶点必须与拼图板上的一个格点重合,两条直角边分别向左和向下。拼图可以重叠在一起。拼图的左下部分可以超过拼图板的边界,如图所示。
  这些拼图有一个好,就是能伸缩,当然,拼图伸缩是要按基本法来的,具体说来就是:你可以选择一个正整数 $k$ ,并使所有拼图的每条边长都变成原来的 $k$ 倍。
  妹子摆好拼图后,ZQC 需要控制一个小人从拼图板的左下角跑到右上角,小人路线上的任何一点(包括端点)都要在某块拼图板上(边界或顶点也可以),现在 ZQC 想知道他的妹子最少要把拼图的边长扩大到原来的几倍才存在一种摆放方式使得他能找到这样一条路线。
 
  为了区分不同的拼图板,图中给他们染了不同的颜色。右图中紫色的线表示小人的一条路线。

输入输出格式:

输入格式:
  第一行两个正整数 $n$ 和 $m$ 表示有 $n$ 块拼图,拼图板边长为 $m$ 。
  接下来 $n$ 行包含两个正整数 $a_i,b_i(1≤a_i,b_i≤1000000)$ ,表示第 $i$ 块拼图初始时的水平直角边长为 $\frac{1}{a_i}$ ,垂直直角边长为 $\frac{1}{b_i}$ 。

输出格式:
  输出一行一个整数 $k$ 表示拼图的边长最少要扩大到原来的 $k$ 倍。

输入输出样例:

样例输入 样例输出
3 20
1 1
2 4
1 6
18

样例解释:

  设 $(x,y)$ 表示拼图板从左下角向右 $x$ 格,向上 $y$ 格的位置,一种方案是三块拼图板的右上角分别在 $(20,20),(20,2),(18,0)$ ,另一种方案是三块拼图板右上角分别在 $(0,17),(3,20),(20,20)$ 。

数据范围:

$1≤n,m≤100$,$1≤a_i,b_i≤1000000$ 。

博主乱搞

蒟蒻解析

  这道题不给部分分差评。。。
  有一个神奇的理论叫做:让最大值最小或让最小值最大的题一般都是二分答案。
  这道题要求的是最大值(能堆出来的最大值)尽量小(但是要大于要求的值)。所以可以考虑二分 $k$ 然后判断是否可行(虽然感觉有点强行解释但的确是这么做的233)。
  还有一件事:怎么判断是否能够覆盖完的问题呢?
  我们可以通过类似背包的动态规划问题来解决。
  我们设 $f[i][j]$ 代表枚举到第 $i$ 个三角板,横向覆盖了 $j$ 的长度,可以得到的最大高度的值。(像不像枚举了第 $i$ 个物品,空间占了 $j$ ,得到物品的最大价值的背包dp?)
  $f[i][j]$ 由谁转移而来?设放大 $k$ 倍的第 $i$ 个三角板的宽度为 $w_max$ ,则 $f[i][j]$ 由 $f[i-1][j-w],\ w\in[0,w_{maxn}]$ 转移而来。
  对应的高度我们也可以根据上面枚举的宽度 $w$ 求出。从而得到转移方程:

$$f[i][j]=max(f[i][j],f[i-1][j-w]+h),\ w\in[0,w_{max}]$$

  至于 $w$ 与 $h$ 的关系,可以画一个三角形手玩一下即可。

蒟蒻代码

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
#define il inline
const int maxn=110;
int n,m;
int a[maxn],b[maxn];
int l=1,r=1000000000,mid,ans;
ll f[maxn][maxn];
bool check(int x){
memset(f,-0x3f,sizeof(f));
f[0][0]=0;
for (int i=1;i<=n;++i){
for (int j=0;j<=m;++j){
for (int w=0;w<=j&&w*a[i]<=x;++w){ //the width
int h=(x-w*a[i])/b[i];
f[i][j]=max(f[i][j],f[i-1][j-w]+h);
}
}
}
return f[n][m]>=m;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i){
scanf("%d%d",&a[i],&b[i]);
}
while (l<=r){
int mid=(l+r)>>1;
if (check(mid)){
ans=mid; r=mid-1;
}else{
l=mid+1;
}
}
printf("%d",ans);
return 0;
}
文章作者: lonlyn
文章链接: https://lonlyn.gitee.io/blog/2019/11/03/loj500/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 lonlyn's blog

评论