重啟usaco.
抽象出模型,可以發現是一個簡單的完全背包問題,復雜度O(N^2+VN).需要考慮幾種特殊情況:
(1)無解
當且僅當n個數中有一個數為1.
(2)惟一解
需要確定的是體積v的最大值.題解中是最大的兩個數的最小公倍數,程序中使用最大數的平方,證明方法不知.
(3)無限解
n個數不互質
1
/**//*
2
ID: liuyupa1
3PROG: nuggets
4LANG: C++
5
*/
6
#include<stdio.h>
7int w[15] = 
{0}, f[66000] = {0};
8int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251};
9void swap(int *x, int *y){
10 int k = *x; *x = *y; *y = k;
11}
12int max(int x, int y){
13 return x>y ? x : y;
14}
15int main(){
16 FILE *fin, *fout;
17 fin = fopen("nuggets.in", "r");
18 fout = fopen("nuggets.out", "w");
19 int n, i, j;
20 fscanf(fin, "%d", &n);
21 for (i = 1; i <= n; i++) fscanf(fin, "%d", &w[i]);
22
for (j = 0; j < 54; j++){
23 int t = 0;
24 for (i = 1; i <= n; i++)
25 if (w[i] % p[j] == 0) t++;
26 if (t == n) {
27 fprintf(fout, "0\n", p[j]);
28 return 0;
29
}
30 }
31 for (i = 1; i < n; i++)
32 for (j = i+1; j <= n; j++)
33 if (w[i] > w[j]) swap(&w[i], &w[j]);
34 if (w[1] == 1){
35 fprintf(fout, "0\n", p[j]);
36 return 0;
37 }
38 for (i = 1; i <= n; i++)
39 for (j = 0; j <= w[n]*w[n]; j++)
40 if (j-w[i] >= 0)
41 f[j] = max(f[j], f[j-w[i]]+w[i]);
42 i = w[n-1]*w[n];
43 while (i > -1 && f[i] == i) i--;
44 fprintf(fout, "%d\n", i);
45 return 0;
46}
47