【가방】【DP】작업

5935 단어 sslDP배낭.

숙제


제목의 대의.


4
  • 서로 다른 숙제는 빛에 대해 비판의 강도가 다르다.i번째 작업이 완성되지 않으면 pi개 단위의 비판을 받아야 한다.여러 번 그러고 나서 연휴 전에 그가 적어도 몇 개 부서의 비판을 받을지 알고 싶었다

    • 샘플 가져오기

    5
3
2 6
1 3
4 7

    출력 예제

    6

    데이터 범위


    4
  • [데이터 범위] 100%의 데이터 중 k<=100000,ti<=10000,pi<=10000;30%의 데이터 중 n<=20;100% 데이터 중 n<=500

    • 문제풀이의 방향


    사실 이 문제는 하나의 배낭으로 총 비판을 가장 많은 소거치를 줄이면 된다.

    절차는 다음과 같다.

    #include
#include
#include
#include
using namespace std;
int n,m,t,p,sum,a[100001];
int main()
{
	freopen("homework.in","r",stdin);
	freopen("homework.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&t,&p);
		sum+=p;//    
		for(int j=n;j>=t;--j)
		{
			a[j]=max(a[j],a[j-t]+p);//     
		}
	}
	printf("%d",sum-a[n]);
	return 0;
}
    SASS 소개
    prettier, eslint 가져올 때 반한 일 2021 새해

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage