昨天晚上寫的一題 結果USACO一直掛中 今天交了下
有一點點的數論知識? 背包很好想 就是不好確定上界
官方題解：
這是一個背包問題。一般使用動態規劃求解。
一種具體的實現是：用一個線性表儲存所有的節點是否可以相加得到的狀態，然后每次可以通過一個可以相加得到的節點，通過加上一個輸入的數求出新的可以相加得到的點。復雜度是O(N×結果)。
但是可以證明結果不會超過最大的兩個數的最小公倍數（如果有的話）。參見數論。所以復雜度也是O(Na2)，完全可以接受了。
判斷無限解可以按上面的方法，另外也可以算所有的數的最大公約數。如果不是1，也就是說這些數不互質，那么不被這個最大公約數整除的數一定構造不出來。當且僅當這種情況會有無限解。另外有一種不需要任何數論知識的方法是判斷是不是按照每個輸入的數的循環節循環，如果是的話，繼續算顯然不會有任何結果。
判斷有沒有更大的解也可以按這種方法，另外如果連續最小的數那么多個數都可以構成，也不會有更大的符合條件的解。
通過位壓縮可以使程序在32位機上的運行速度快32倍（由于程序代碼會變長，也可能是16倍或者更小的倍數）。這樣可以相當快的解決這個問題。不過復雜度還是O(Na2)。
“可以證明結果不會超過最大的兩個數的最小公倍數”。我來證明一下。
已知，不定方程 ax + by = c ( a , b > 0 且 c >= ab )存在一組整數解( x0 , y0 ) (斐蜀定理) 求證，該不定方程存在一組非負整數解 ( xn , yn ) . 證明 : 由不定方程通解式得 : xn = x0 + b * t , yn = y0 - a * t ( t 是整數 ) 令 xn , yn >= 0 解出 - ( x0 / b ) <= t <= ( y0 / a ) 因為 c >= a * b 即 a * x0 + b * y0 >= a * b 兩邊同除 a * b 得 : y0 / a - ( - x0 / b ) >= 1 所以一定存在 整數t使得 - ( x0 / b ) <= t <= ( y0 / a ) . 所以方程一定有非負整數解. 證畢.
特殊情況
- 無解的情況：很顯然，只有輸入的N個數里有1的情況才會無解，否則1本身就是一個解，因為沒辦法由更大的數相加得到。
- 無限個解的情況，見上面的#問題分析。
對于這道題目，這兩種情況都應該輸出0。
注：如果有兩個連續的數x,x+1 在序列中的話，那(x-1)*x以后的數都能通過這兩個相加得到。所以如果（x-1）*x前無解，則無解!
1 /* 2 ID: shangca2 3 LANG: C++ 4 TASK: nuggets 5 */ 6 7 #include <iostream> 8 #include<cstdio> 9 #include<cstring> 10 #include<algorithm> 11 #include<stdlib.h> 12 using namespace std; 13 #define N 70000 14 int dp[70010]; 15 int a[12]; 16 int gcd(int a,int b) 17 { 18 return b==0?a:(gcd(b,a%b)); 19 } 20 int main() 21 { 22 freopen("nuggets.in","r",stdin); 23 freopen("nuggets.out","w",stdout); 24 int i,j,n,y; 25 cin>>n; 26 for(i = 1; i <= n ; i++) 27 cin>>a[i]; 28 y = a[1]; 29 if(n==1) 30 { 31 printf("0\n"); 32 return 0; 33 } 34 for(i = 2; i <= n ; i++) 35 { 36 y = gcd(y,a[i]); 37 } 38 if(y!=1) 39 { 40 puts("0"); 41 return 0; 42 } 43 int v = N; 44 dp[0] = 1; 45 for(j = 1; j <= n ; j++) 46 for(i = a[j] ; i <= v ; i++) 47 { 48 dp[i] = max(dp[i],dp[i-a[j]]); 49 } 50 for(i = v ; i>=1 ; i--) 51 { 52 if(dp[i]==0) 53 break; 54 } 55 if(i==0) 56 cout<<"0\n"; 57 else 58 cout<<i<<endl; 59 return 0; 60 }
?
)
的小例子)
)