link:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=615
和完全背包一样的思想。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <cctype> 7 #include <algorithm> 8 #include <queue> 9 #include <deque> 10 #include <queue> 11 #include <list> 12 #include <map> 13 #include <set> 14 #include <vector> 15 #include <utility> 16 #include <functional> 17 #include <fstream> 18 #include <iomanip> 19 #include <sstream> 20 #include <numeric> 21 #include <cassert> 22 #include <ctime> 23 #include <iterator> 24 const int INF = 0x3f3f3f3f; 25 const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}}; 26 using namespace std; 27 int a[5]={1,5,10,25,50}; 28 int f[7777]; 29 int main(void) 30 { 31 ios::sync_with_stdio(false); 32 #ifndef ONLINE_JUDGE 33 freopen("in.txt","r",stdin); 34 #endif 35 int n; 36 while (cin>>n) { 37 memset(f,0,sizeof(f)); f[0]=1; 38 for (int i = 0; i < 5; ++i) { 39 for (int j=a[i]; j<=n;++j) { 40 f[j]+=f[j-a[i]]; 41 } 42 } 43 cout<<f[n]<<endl; 44 } 45 return 0; 46 }
o(╯□╰)o
认真理解一下这种思想就行了。不难