|
|
题目链接：http://poj.org/problem?id=3492
  /**//*
 题意：
给出n(n <= 500)个数ai(ai <= 5000)，求他们的最大不能组合数。
解法：
数论 + 最短路
思路：
经典的组合问题Change Making Problem，这个题目有一个限制就是给
定的数小于等于5000，题目的意思很清楚，就是求一个数S，使得它不能被
任何ai的倍数所组合出来，并且它的值最大。
那么如果这n个数的gcd不为1，必然找不到这样的S，因为如果S不能被
它们的gcd整除，永远不可能组合出来，这样S就可以很大，自然也就没有最
大的S了。
现在讨论所有ai的gcd为1的情况。对于任意的整数A，如果A能被以上的
ai组合出来，那么 B = A + k*a0 必然能被组合（只要加上k个a0即可）。于
是我们可以吧所有整数划分成a0个等价类，等价类中的数模a0的值相同，举
个例子，a0=3，我们可以将0,1,2,3,4,5,6划分成(0,3,6)(1,4)(2,5)这三个
等价类，如果相同等价类中的某个数能被组合，那么比它大的所有在该等价
类中的数必然能被组合出来。所以现在只要求出每个等价类中的最小的能被
组合出来的数，然后取所有等价类中最小数的最大值L，L-a[0]就是问题的
答案（原因很简单，因为L能被组合出来，比L大的并且在同一等价类中的数
必然能通过加上若干个a[0]来求得，于是L-a[0]就成了最大不能组合数）。
于是问题就转化成了如何在相同等价类中找到最小的那个能被ai组合出
来的数。可以利用最短路来求，最短路的key信息就是它本身值的大小，如果
两个数x,y, (x + ai) % a0 == y % a0，那么我们就在x和y之前连上一条权
值为ai的边，构图完成后就可以从0这个点开始搜了，最后遍历0到a[0]-1找
到最大的那个数L即可。
 */
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define maxn 5010
#define inf 200000000
int a[500];
struct Point  {
int val;
int mod_val;
int dis;
  Point(int _v, int _mv, int _d) {
val = _v;
mod_val = _mv;
dis = _d;
 }
friend bool operator < (Point a, Point b) {
return a.dis > b.dis;
}
};
int dis[maxn], nv[maxn];
priority_queue < Point > Q;
int gcd(int a, int b) {
if(b == 0)
return a;
return gcd(b, a%b);
}
int main() {
int n;
int i;
while(scanf("%d", &n) != EOF) {
int G = 0;
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
if(!i)
G = a[0];
else
G = gcd(G, a[i]);
}
if(G != 1) {
printf("INF\n");
continue;
}
sort(a, a + n);
for(i = 0; i < a[0]; i++) {
dis[i] = inf;
}
dis[0] = 0;
nv[0] = 0;
while(!Q.empty()) {
Q.pop();
}
Q.push(Point(0, 0, 0));
while(!Q.empty()) {
Point id = Q.top();
Q.pop();
for(i = 0; i < n; i++) {
int nex = (id.mod_val + a[i]) % a[0];
if(id.dis + a[i] < dis[nex]) {
dis[nex] = id.dis + a[i];
nv[nex] = id.val + a[i];
Q.push(Point(nv[nex], nex, dis[nex]));
}
}
}
int Max = 0;
for(i = 0; i < a[0]; i++) {
if(dis[i] != inf && nv[i] > Max) {
Max = nv[i];
}
}
printf("%d\n", Max - a[0]);
}
return 0;
}
|