|
|
題目鏈接：http://poj.org/problem?id=3492
  /**//*
 題意：
給出n(n <= 500)個(gè)數(shù)ai(ai <= 5000)，求他們的最大不能組合數(shù)。
解法：
數(shù)論 + 最短路
思路：
經(jīng)典的組合問(wèn)題Change Making Problem，這個(gè)題目有一個(gè)限制就是給
定的數(shù)小于等于5000，題目的意思很清楚，就是求一個(gè)數(shù)S，使得它不能被
任何ai的倍數(shù)所組合出來(lái)，并且它的值最大。
那么如果這n個(gè)數(shù)的gcd不為1，必然找不到這樣的S，因?yàn)槿绻鸖不能被
它們的gcd整除，永遠(yuǎn)不可能組合出來(lái)，這樣S就可以很大，自然也就沒(méi)有最
大的S了。
現(xiàn)在討論所有ai的gcd為1的情況。對(duì)于任意的整數(shù)A，如果A能被以上的
ai組合出來(lái)，那么 B = A + k*a0 必然能被組合（只要加上k個(gè)a0即可）。于
是我們可以吧所有整數(shù)劃分成a0個(gè)等價(jià)類，等價(jià)類中的數(shù)模a0的值相同，舉
個(gè)例子，a0=3，我們可以將0,1,2,3,4,5,6劃分成(0,3,6)(1,4)(2,5)這三個(gè)
等價(jià)類，如果相同等價(jià)類中的某個(gè)數(shù)能被組合，那么比它大的所有在該等價(jià)
類中的數(shù)必然能被組合出來(lái)。所以現(xiàn)在只要求出每個(gè)等價(jià)類中的最小的能被
組合出來(lái)的數(shù)，然后取所有等價(jià)類中最小數(shù)的最大值L，L-a[0]就是問(wèn)題的
答案（原因很簡(jiǎn)單，因?yàn)長(zhǎng)能被組合出來(lái)，比L大的并且在同一等價(jià)類中的數(shù)
必然能通過(guò)加上若干個(gè)a[0]來(lái)求得，于是L-a[0]就成了最大不能組合數(shù)）。
于是問(wèn)題就轉(zhuǎn)化成了如何在相同等價(jià)類中找到最小的那個(gè)能被ai組合出
來(lái)的數(shù)?？梢岳米疃搪穪?lái)求，最短路的key信息就是它本身值的大小，如果
兩個(gè)數(shù)x,y, (x + ai) % a0 == y % a0，那么我們就在x和y之前連上一條權(quán)
值為ai的邊，構(gòu)圖完成后就可以從0這個(gè)點(diǎn)開(kāi)始搜了，最后遍歷0到a[0]-1找
到最大的那個(gè)數(shù)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;
}
|