学步园

dp

#include <iostream><br /> #include <cmath><br /> #include <cstring><br /> using namespace std;<br /> int N, m;<br /> int data[30000];<br /> int main() {<br /> while(cin >> N >> m) {<br /> int ans = 0;<br /> int cost, pro;<br /> memset(data, 0, sizeof(data));<br /> for(int i = 0; i < m; i++) {<br /> cin >> cost >> pro;<br /> for(int j = N; j >= cost; j--) {<br /> if(data[j] < data[j - cost] + cost * pro) {<br /> data[j] = data[j - cost] + + cost * pro;<br /> ans = max(data[j], ans);<br /> }<br /> }<br /> }<br /> cout << ans << endl;<br /> }<br /> return 0;<br /> }