hdu 4508 추 추 시리즈 이야기 - 다이어트 I

추 추 시리즈 - 다이어트 기 I
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2518    Accepted Submission(s): 1291
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
   
   
   
   
   
   
   
   

    
    
    
    /*  ：
          ，       。 
*/

   
   
   
   
   
   
   
   

    
    
    
    
#include<cstdio>
#include<cstring>
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int n,m,i,j,w[100010],val[100010],dp[100010];
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        for(i=1; i<=n; i++)
        {
            scanf("%d %d",&val[i],&w[i]);
        }
        scanf("%d",&m);
        for(i=1; i<=n; i++)
        {
            for(j=w[i]; j<=m; j++)
            {
                dp[j]=max(dp[j],dp[j-w[i]]+val[i]);
            }
        }
        printf("%d
",dp[m]);
    }
    return 0;
}