HihoCoder#1043 전체 가방

3218 단어 code
원제 주소
 
기본 동적 기획 문제 + 상태 압축
힌트를 보고는 도리어 할 줄 모른다.
 
코드:
 1 #include <iostream>

 2 

 3 using namespace std;

 4 

 5 int main() {

 6   int N, M;

 7   int best[500010] = {0};

 8   int value[512];

 9   int need[512];

10 

11   cin >> N >> M;

12   for (int i = 0; i < N; i++)

13     cin >> need[i] >> value[i];

14 

15   for (int i = N - 1; i >= 0; i--) {

16     for (int j = 1; j <= M; j++) {

17       if (j >= need[i])

18         best[j] = max(best[j], best[j - need[i]] + value[i]);

19     }

20   }

21 

22   cout << best[M] << endl;

23 

24   return 0;

25 }

좋은 웹페이지 즐겨찾기