HDU 1248 한 빙 왕좌 (풀 백: 입문 문제)
2036 단어 HDU
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.