HDU 4508 추 추 시리즈 이야기 - 다이어트 기 i - 간단 한 완전 가방

Problem Description
먹 는 사람 에 게 설 을 쇠 는 가장 행복 한 일 은 먹 는 것 이다. 하나 도 없다!
하지만 여자 에 게 칼 로 리 는 천적 이 야!
베테랑 미녀 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추 추
물론 식단 을 만 드 는 데 편 의 를 위해 추 추 추 는 매일 음식 목록 을 주 었 다. 그 위 에 그날 먹고 싶 은 모든 음식 이 그녀 에 게 주 는 행복 정도 와 칼 로 리 를 증가 시 킬 수 있다 는 것 을 묘사 했다.
 
Input
여러 그룹의 테스트 용례 를 입력 하 십시오.
각 조 의 데 이 터 는 하나의 정수 n 으로 시작 하여 매일 음식 목록 에 n 가지 음식 이 있다 는 것 을 나타 낸다. 
그 다음 에 n 줄 에 두 개의 정수 a 와 b 가 있 는데 그 중에서 a 는 이런 음식 이 추 추 추 에 게 가 져 다 줄 수 있 는 행복 치 (수치 가 클 수록 행복) 를 나타 낸다. b 는 추 추 추 가 이런 음식 을 먹 으 면 흡수 되 는 칼 로 리 를 나타 낸다.
마지막 으로 정수 m 는 추 추 추 가 하루 에 흡수 하 는 칼 로 리 는 m 를 초과 해 서 는 안 된다 는 것 을 나타 낸다.
  
[Technical Specification]
  1. 1 <= n <= 100
  2. 0 <= a,b <= 100000
  3. 1 <= m <= 100000
 
Output
모든 목록 에 대해 하나의 정 수 를 출력 하 는 것 은 칼로리 흡수 량 을 만족 시 키 는 동시에 추 추 추 는 얻 을 수 있 는 최대 행복 치 이다.
 
Sample Input

   
   
   
   
3 3 3 7 7 9 9 10 5 1 1 5 3 10 3 6 8 7 5 6

 
Sample Output

   
   
   
   
10 20

 
//Must so
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<ctype.h>
#include<queue>
#include<vector>
#include<set>
#include<cstdio>
#include<cmath>
#define mem(a,x) memset(a,x,sizeof(a))
#define inf 1<<30
#define NN 100005
using namespace std;
const double PI = acos(-1.0);
typedef long long LL;

/**********************************************************************
      01  ,                 
              
**********************************************************************/

int dp[NN];
int c[111],w[111];
int main()
{
    int N;
    while (cin>>N)
    {
        for (int i = 1;i <= N;i++)
            scanf("%d%d",&w[i],&c[i]);
        int V;
        cin>>V;
        mem(dp,0);
        for (int i = 1;i <= N;i++)
        {
            for (int j = c[i];j <= V;j++)//     01                  
                dp[j] = max(dp[j],dp[j-c[i]]+w[i]);
        }
        cout<<dp[V]<<endl;
    }
    return 0;
}

좋은 웹페이지 즐겨찾기