题目大意
ZQC和他的妹子在玩拼图。她们有$n(1\le n\le100)$块神奇的拼图，还有一块拼图板。拼图板是一个$m\times m(1\le m\le100)$的正方形网格，每格边长为$1$，如图所示。每块拼图都是直角三角形，正面为白色，反面为黑色，拼图放在拼图板上时，必须正面朝上，直角顶点必须与拼图板上的一个格点重合，两条直角边分别向左和向下。拼图可以重叠在一起。拼图的左下部分可以超过拼图板的边界，如图所示。
这些拼图有一个好，就是能伸缩，当然，拼图伸缩是要按基本法来的，具体说来就是：你可以选择一个正整数$k$，并使所有拼图的每条边长都变成原来的$k$倍。
妹子摆好拼图后，ZQC需要控制一个小人从拼图板的左下角跑到右上角，小人路线上的任何一点（包括端点）都要在某块拼图板上（边界或顶点也可以），现在ZQC想知道他的妹子最少要把拼图的边长扩大到原来的几倍才存在一种摆放方式使得他能找到这样一条路线。
为了区分不同的拼图板，图中给他们染了不同的颜色。右图中紫色的线表示小人的一条路线。
题目分析
题解讲得较为详细，在这里做一些补充：
首先关于条件
的推导如下：
对于前两个式子显然，第三个式子推导如下：
记$\Delta x=x_i-x_{i-1}$，$\Delta y$同理。
当上一个点在三角形斜边上时：
根据相似三角形可知：
故：
即：
当上一个点在三角形内部时：
即：
因此我们可以二分$k$，设置状态$f[i,j]$表示前$i$块拼图，横坐标到达$j$时纵坐标的最大值。
转移方程即为：
根据上述的推导，可以保证向下取整的时候一定对应一个合法解。
检验$f[n,m]$是否不小于$m$即可，时间复杂度$O(nm^2\log a)$。
代码
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=105;
int n,m,a[maxn],b[maxn],f[maxn][maxn];
bool Check(int K) {
f[0][0]=0;
for(int i=1; i<=n; i++)
for(int j=0; j<=m; j++) {
f[i][j]=-INT_MAX/2;
for(int k=max(0,j-K/a[i]); k<=j; k++)
f[i][j]=max(f[i][j],f[i-1][k]+(K-a[i]*(j-k))/b[i]);
}
return f[n][m]>=m;
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
b[i]=Get_Int();
}
for(int i=1; i<=m; i++)f[0][i]=-INT_MAX/2;
int Left=1,Right=100000000;
while(Left<=Right) {
int mid=(Left+Right)>>1;
if(Check(mid))Right=mid-1;
else Left=mid+1;
}
printf("%d\n",Left);
return 0;
}
|
