|
|
題目鏈接：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;
}
|