글 읽기 - 평범한 배낭과 똑같은..

dk10211 2년 전 0

해당 item을 몇번 썼는지 개수만 저장해두고 개수가 부족해지면 하나 버리고 저장하면 AC 받는데 이게 플레 4의 난이도가 맞나요?

그저 앞에서 해당 item을 사용하는게 이득이였다면 뒤에서도 최대한 많이 사용하는 방향으로 간다는 아이디어인데..

#include<bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef struct{

	int W,U,C;	double key;

}bg;

int main(){

	ios_base::sync_with_stdio(false),cin.tie(0);

	int n,m;cin>>n>>m;

	vector<bg>v(n);

	for(int i=0;i<n;i++){

		cin>>v[i].W>>v[i].U>>v[i].C;

		v[i].key=(double)v[i].U/(double)v[i].W;

	}

	sort(v.begin(),v.end(),[](bg a,bg b)->bool {return a.key>b.key;});

	vector<pair<int,int>>a(m+1);

	for(auto cur:v){

		vector<pair<int,int>>t=a;

		for(int i=0;i<=m;i++) t[i].Y=0;

		for(int i=cur.W;i<=m;i++){

			int j=i-cur.W;

			if(t[j].X+cur.U>a[i].X){

				if(t[j].Y<cur.C){

					t[i].Y=t[j].Y+1;

					t[i].X=t[j].X+cur.U;

				}

				else{

					j=i-cur.W*cur.C;

					t[i]={a[j].X+cur.U*cur.C,cur.C};

				}

			}

		}

		a=t;

	}

	cout<<a[m].X;

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

평범한 배낭과 똑같은..

dk10211 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말