学步园

这题用过三种方法。。堪称神题啊

//母函数<br /> #include <iostream><br /> #include <cstring><br /> using namespace std;<br /> int m1[301],m2[301];<br /> int c[8];<br /> int n;<br /> int count;<br /> int main() {<br /> cin >> n >> count;<br /> for(int i = 0; i < count; i++)<br /> cin >> c[i];<br /> for(int i = 0; i <= n; i += c[0]) m1[i] = 1;<br /> memset(m2, 0, sizeof(m2));<br /> for(int i = 1; i < count; i++) {<br /> for(int j = 0; j <= n; j++)<br /> for(int k = 0; k + j <= n; k += c[i])<br /> m2[k + j] += m1[j];<br /> for(int j = 0; j <= n; j++) {<br /> m1[j] = m2[j];<br /> m2[j] = 0;<br /> }<br /> }<br /> cout << m1[n] << endl;<br /> return 0;<br /> }<br /> //dp完全背包<br /> //#include <iostream><br /> //#include <cstring><br /> //using namespace std;<br /> //<br /> //int f[301];<br /> //int n, c;<br /> //<br /> //int main() {<br /> // while(cin >> n >> c) {<br /> // memset(f, 0, sizeof(f));<br /> // f[0] = 1;<br /> // for(int i = 0; i < c; i++){<br /> // int tmp;<br /> // cin >> tmp;<br /> // for(int j = tmp; j <= n; j++) {<br /> // f[j] += f[j - tmp];<br /> // }<br /> // }<br /> // cout << f[n] << endl;<br /> // }<br /> // return 0;<br /> //}<br /> ////搜索<br /> //#include <iostream><br /> //using namespace std;<br /> //<br /> //int n, c, count;<br /> //int coins[300];<br /> //void _find(int sum, int cur) {<br /> // sum -= coins[cur];<br /> // for(int i = 0; (sum = sum + coins[cur]) <= n; i++) {<br /> // if(sum == n) {<br /> // count++;<br /> // return;<br /> // }<br /> // if(cur < c - 1) _find(sum, cur + 1);<br /> // }<br /> //}<br /> //int main() {<br /> // while(cin >> n >> c) {<br /> // for(int i = 0; i < c; i++) cin >> coins[i];<br /> // count = 0;<br /> // _find(0, 0);<br /> // cout << count << endl;<br /> // }<br /> // return 0;<br /> //}<br />