HDU 1248 한 빙 왕좌 (풀 백: 입문 문제)

2036 단어 HDU
HDU 1248 한 빙 왕좌 (풀 백: 입문 문제)
http://acm.hdu.edu.cn/showproblem.php?pid=1248
제목:
       불사 족의 요괴 왕 은 월급 을 주 고 사망 기 사 는 N 원 짜 리 지 폐 를 받 았 다.
죽음 의 기사: "나 는 도 구 를 살 거 야!"
임 프 상인: "우리 에 게 는 세 가지 도구 가 있 습 니 다. 혈액 병 150 원, 마법 약 200 원, 무적 물약 350 원 입 니 다."
죽음 의 기사: "네, 혈액 병 하나 주세요."
말 이 떨 어 지자 그 는 N 원 짜 리 큰 지 폐 를 꺼 내 임 프 상인 에 게 건 네 주 었 다.
임 프 상인: "손님 에 게 돈 을 찾 는 습관 이 없다 는 걸 깜빡 했 네. 많은 돈 은 팁 으로 받 았 네. 헤헤."
죽음 의 기사: "....."
죽음 의 기 사 는 돈 을 팁 으로 주 느 니 차라리 자신 이 도 구 를 좀 더 사 는 것 이 낫 겠 다 고 생각 했다. 어차피 앞으로 사 야 할 것 이 니 일찍 사서 집에 두 는 것 도 좋 지만 팁 을 적 게 벌 게 해 야 한다 고 생각 했다.
이제 죽음 의 기 사 는 임 프 상인 에 게 최소한 얼마의 팁 을 줄 지 계산 해 달라 고 한다.
분석:
       3 가지 상품 만 있 고 무한 공급 되 어 있어 가방 문제 가 뚜렷 하 다.
       본 문제 제한 조건: 총 비용 < = N
       본 문제 목표 조건: 총 비용 은 가능 한 한 크다.
       dp [i] [j] = x 는 전 i 가지 상품 만 구 매 할 때 총 < = j 위안 을 쓸 때 최대 x 위안 을 쓸 수 있다 고 표시 합 니 다.
       초기 화: dp 는 모두 0 입 니 다.
       상태 이동: dp [i] [j] = max (dp [i - 1] [j], dp [i] [j - val [i]]] + val [i])
       전 자 는 i 번 째 상품 을 하나 도 사지 않 는 다 고 밝 혔 고 후 자 는 적어도 1 번 째 상품 을 사 겠 다 고 밝 혔 다.
       마침내 원 하 는 것: dp [n] [N]. n 은 상품 수 이 고 본 제 는 n = = 3. N 은 초기 금전 수량 입 니 다. 그러나 우 리 는 N - dp [n] [N] 을 수출 해 야 합 니 다.
       프로그램 이 사용 하 는 스크롤 배열 이 므 로 dp 는 [j] 1 차원 만 있 습 니 다.
AC 코드:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10000+5;

int n=3;
int val[]={150,200,350};//      
int dp[maxn];

int main()
{
    //   
    memset(dp,0,sizeof(dp));

    //  
    for(int i=0;i<n;i++)
    {
        for(int j=val[i];j<maxn;j++)
            dp[j] = max(dp[j], dp[j-val[i]]+val[i]);
    }

    //         
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int x;
        scanf("%d",&x);
        printf("%d
",x-dp[x]); } return 0; }

좋은 웹페이지 즐겨찾기