【bzoj 1407】【Noi2002】Savage

Description

Input

第1行为一个整数N(1<=N<=15)，即野人的数目。

第2行到第N+1每行为三个整数Ci, Pi, Li表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。

(1<=Ci,Pi<=100, 0<=Li<=10^6 )

Output

仅包含一个数M，即最少可能的山洞数。输入数据保证有解，且M不大于10^6。

Sample Input

3
1 3 4
2 7 3
3 2 1

Sample Output

6
//该样例对应于题目描述中的例子。

题解：

　　看到这题好久了，一直心虚不敢上= =（其实是自己想多了）。

　　一开始以为可以直接算出来，其实也是自己想多了……给了m的范围，n的范围又极其小……然后就是从小到大枚举m，利用扩欧验证是否可行。

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 const int N=20;
 5 int n, m;
 6 int c[N],p[N],l[N];
 7 inline int abs(int x){return (x&-1)?-x:x;}
 8 inline int gcd(int a,int b){
 9     return b==0?a:gcd(b,a%b);
10 }
11 inline void exgcd(int a,int b,int &x,int &y){
12     if(b==0) {
13         x=1;
14         y=0;
15         return;
16     }
17     exgcd(b,a%b,x,y);
18     int temp=x;
19     x=y;
20     y=temp-a/b*y;
21     return ;
22 }
23 inline bool check(int mod){
24     for(int i=1;i<=n;i++)
25         for(int j=i+1;j<=n;j++){
26             int a=p[i]-p[j],b=mod,z=c[j]-c[i];
27             int t=gcd(a,b);
28             if(z%t)  continue;
29             int x,y;
30             exgcd(a,b,x,y);
31             x=x*z/t;
32             x%=b/t;
33             if(x<0)
34                 x+=abs(b/t);
35             if(x<=l[i]&&x<=l[j])    return false;
36         }
37     return true;
38 }
39 int main(){
40     scanf("%d", &n);
41     int m=0;
42     for(int i=1;i<=n;i++)
43         scanf("%d%d%d",c+i,p+i,l+i),m=max(m,c[i]);
44     for(m;m<=(int)1e6;m++){
45         if(check(m))   break;
46     }
47     printf("%d
",m);
48 }
49 /*
50 3
51 1 3 4
52 2 7 3
53 3 2 1
54 */