작성한 질문수 30

4

안녕하세요^^

개수가 유한개이면 뒤에서 부터 참조하면 됩니다.

최대점수 구하기 문제를 개수까지 넣은 문제로 바꾸어보면

5 20

11 5 6  //점수, 시간, 개수

25 12 2

15 8 3

6 3 6

7 3 4

라면 답은 11+6+(7*4)=45입니다.

코드구현은 다음과 같습니다. 이런 문제가 저지사이트에 있다면 검증을 해보겠는데, 아마 반례는 없을 겁니다. 해보시고 반례가 있으면 얘기해주세요.

#include<bits/stdc++.h>
using namespace std;
int main() {
	freopen("input.txt", "rt", stdin);
	ios::sync_with_stdio(false);
	int n, m, ps, pt, pc;
	cin>>n>>m;
	vector<int> dy(m+1);
	for(int i=0; i<n; i++){
		cin>>ps>>pt>>pc;
		for(int j=m; j>=pt; j--){
			for(int k=1; k<=pc; k++){
				if(j-pt*k<0) break;
				dy[j]=max(dy[j], dy[j-pt*k]+ps*k);
			}			
		}			
	}
	cout<<dy[m]<<"\n";		
	return 0;
}