hdu 4501 샤 오 밍 시리즈 이야기 - 설 맞이 다 중 가방 사기

샤 오 밍 시리즈 이야기 - 설 맞이 용품 사기
                                                                         Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Problem Description
설 이 다가 오자 샤 오 밍 은 슈퍼마켓 에 가서 설 맞이 물건 을 사려 고 하 자 샤 오 밍 은 자신 이 자주 가 는 도상 슈퍼마켓 에 갔다.
슈퍼마켓 에 도착 하 자마자 샤 오 밍 은 슈퍼마켓 입구 에 한 무리의 사람들 이 모 이 는 것 을 발견 했다.백운 여사 의 말 에 따 르 면 "그 녀석, 그 장면 은 정말 인산 인 해 를 이 루 었 다. 징 과 북 이 요란 하고 폭죽 이 치 린 을 울 리 며 붉 은 깃발 이 흔 들 렸 다. 그것 은 정말 장관 이 었 다."궁금 한 샤 오 밍 은 사람들 을 밀치 고 지나 가 는데 슈퍼마켓 입구 에 알림 이 붙 어 있 는 것 을 발견 했다. 내용 은 다음 과 같다.
　　
　　
설 명절 을 앞 두 고 많은 고객 들 의 지지 와 사랑 에 보답 하기 위해 설 맞이 대 사례, 할인 대 방송 행 사 를 개최한다.모든 도상 회원 은 회원 포인트 로 상품 을 교환 할 수 있 고 도상 회원 은 모두 무료 로 k 개의 상품 을 받 을 수 있 으 며 쇼핑 고객 은 모두 좋 은 선물 을 줄 수 있다.100 원 을 채 우 면 bla bla bla, 200 원 을 채 우 면 bla bla bla... blablablabla..........................................
　　
통 지 를 다 읽 기도 전에 샤 오 밍 은 기뻐 서 죽 을 지경 이 었 다. 왜냐하면 그 가 바로 도상 의 회원 이기 때문이다.잠시 도 지체 하지 않 은 샤 오 밍 은 슈퍼마켓 을 한 바퀴 둘 러 보 았 는데 슈퍼마켓 에 그 가 원 하 는 상품 이 n 개 있 는 것 을 발견 했다.샤 오 밍 은 이 n 개의 상품 에 대해 점 수 를 매 겨 상품 의 실제 가 치 를 나 타 냈 다.샤 오 밍 은 v1 의 인민 폐 를 가지 고 있 고 회원 카드 안에 v2 의 포인트 가 있다 는 것 을 발견 했다.그 는 그 가 가장 많은 가치 의 상품 을 살 수 있 는 지 알 고 싶 어 한다.
샤 오 밍 이 원 하 는 상품 이 너무 많아 서 그 는 한참 동안 머리 가 아파 도 계산 하지 못 했 으 니 이 똑똑 한 프로그래머 에 게 그 를 도와 달라 고 부탁 했다.
 
Input
여러 그룹의 테스트 용례 를 입력 하 십시오.
각 그룹의 데이터 의 첫 줄 은 네 개의 정수 n, v1, v2, k 이다.
그 다음 에 n 줄, 줄 당 3 개의 정수 a, b, val 은 각 상품 의 가격, 교환 에 필요 한 포인트, 실제 가 치 를 나타 낸다.
[Technical Specification]
1 <= n <= 100
0 <= v1, v2 <= 100
0 <= k <= 5
0 <= a, b, val <= 100
P. 돈 이나 포인트 가 한 상품 을 구 매 하 는 요 구 를 만족 시 키 면 이 상품 을 살 수 있 습 니 다.
 
Output
각 그룹의 데이터 에 대해 출력 이 살 수 있 는 최대 가치.
자세 한 정 보 는 Sample 참조.
 
Sample Input

   
   
   
   

    
    
    
    5 1 6 1
4 3 3
0 3 2
2 3 3
3 3 2
1 0 2
4 2 5 0
0 1 0
4 4 1
3 3 4
3 4 4
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    12
4
   
   
   
   
   
   
   
   
    
    
    
    
              。      ：dp[v1][v2][k]=MAX(dp[v1-a][v2][k]+c,dp[v1][v2-b][k]+c,dp[v1][v2][k-1]+c).
   
   
   
   
   
   
   
   

    
    
    
    /*dp[j][k][t]   j  ，  k   ，    t          */ 
   
   
   
   
   
   
   
   

    
    
    
    AC  ：
   
   
   
   
   
   
   
   

    
    
    
    
/*dp[j][k][t]   j  ，  k   ，    t          */
#include<stdio.h>
#include<string.h>
int dp[102][102][10],a[102],b[102],val[102];
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int n,i,v1,v2,j,k,t,p,MAX;
    while(scanf("%d%d%d%d",&n,&v1,&v2,&p)!=EOF) //n     ，v1   ，v2    ，p        
    {
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
            scanf("%d%d%d",&a[i],&b[i],&val[i]); //a[i]            ，b[i]            ，val[i]        
        for(i=0;i<n;i++)
            for(j=v1;j>=0;j--)
                for(k=v2;k>=0;k--)
                    for(t=p;t>=0;t--)
                    {
                        int MAX=0; //            0
                        if(j>=a[i])  //    
                          MAX=max(MAX,dp[j-a[i]][k][t]+val[i]);  //        
                        if(k>=b[i]) //      
                            MAX=max(MAX,dp[j][k-b[i]][t]+val[i]); //          
                        if(t>=1)  //    
                            MAX=max(MAX,dp[j][k][t-1]+val[i]); //        
                        dp[j][k][t]=max(dp[j][k][t],MAX);  //              
                    }
                printf("%d
",dp[v1][v2][p]);  // v1   v2         k         
    }
    return 0;
}