枚举答案, 然后O(N^2)枚举野人去判他们是否会在有生之年存在同山洞. 具体做法就是: 设第x年相遇, 则 Ci+x*Pi=Cj+x*Pj (mod M), 然后解同余方程. 复杂度应该是O(ans*N^2log(ans)), 但是实际远小于....能够AC
--------------------------------------------------------------------
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 20;
int N, p[maxn], c[maxn], l[maxn], ans;
void Init() {
ans = 0;
scanf("%d", &N);
for(int i = 0; i < N; i++) {
scanf("%d%d%d", c + i, p + i, l + i);
ans = max(ans, c[i]);
}
}
void Gcd(int a, int b, int &d, int &x, int &y) {
if(!b) {
d = a;
x = 1;
y = 0;
} else {
Gcd(b, a % b, d, y, x);
y -= x * (a / b);
}
}
bool chk() {
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++) if(p[i] > p[j]) {
int d, x, y;
Gcd(p[i] - p[j], ans, d, x, y);
if((c[j] - c[i]) % d)
continue;
int t = ans / d;
x *= (c[j] - c[i]) / d;
while(x >= 0) x -= t;
while(x < 0) x += t;
if(x <= l[i] && x <= l[j])
return false;
}
return true;
}
void Work() {
while(!chk())
ans++;
printf("%d\n", ans);
}
int main() {
Init();
Work();
return 0;
}
--------------------------------------------------------------------
1407: [Noi2002]Savage
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1102 Solved: 501
[Submit][Status][Discuss]
Description
Input
第1行为一个整数N(1<=N<=15)，即野人的数目。第2行到第N+1每行为三个整数Ci, Pi, Li (1<=Ci,Pi<=100, 0<=Li<=106 )，表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。
Output
仅包含一个数M，即最少可能的山洞数。输入数据保证有解，且M不大于106。
Sample Input
3
1 3 4
2 7 3
3 2 1
1 3 4
2 7 3
3 2 1
Sample Output
6
该样例对应于题目描述中的例子。