HDU-1260 Tickets 간단한 질문(동적 계획/DP+ 간단한 시뮬레이션)

1709 단어 동적 기획
제목:
현재 n명이 영화표를 사려고 하는데 한 사람당 단독으로 표를 사는 데 걸리는 시간, 그리고 전 사람과 함께 사는 데 걸리는 시간을 알고 있다면 최소한 얼마나 걸리면 표를 다 살 수 있는지 물어보세요.
Input
N(1<=N<=10)을 주면 N팀의 샘플이 있고 K(1<=K<=2000)를 주면 K 개인이 표를 샀다는 뜻인데...K 개수를 드리면 이 사람이 단독으로 표를 사는데 걸리는 시간을...개수(0s<=Si<=25s)마다 K-1을 주어 이 사람과 앞에 있는 사람이 표를 사는 데 걸리는 시간을 표시한다..개수 보장 (0s<=Si<=50s)
Output
각 조의 데이터에 대해 당신은 영화관의 매표가 끝날 시간을 제시해야 합니다. 매표 시작 시간은 08:00:00 am입니다.시간 형식: HH:MM:SS am|pm.구체적으로 보기 샘플 출력
Sample Input 
2
2
20 25
40
1
8

Sample Output 
08:00:40 am
08:00:08 am

사고방식: 한 개의 수조로 표를 사는 시간, 한 개의 수조로 현재 사람과 전 사람이 함께 사는 시간을 저장하면 DP 방정식은 쉽게 추측할 수 있다. 그 다음에 모의하는 과정이다. 여기서 나는 먼저 전체 시간, 분, 초를 계산한 다음에 지난 오후의 변동을 확정한 다음에 HH:MM:SS를 6개의 1~9개의 숫자로 각각 출력한다. 코드는 전체적인 난이도가 크지 않다. 나의 코드:
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int t,k,a[2005],d[2005],dp[2005];
int main()
{
	cin>>t;
	while(t--){
		cin>>k;
		for(int i=1;i<=k;i++){
			scanf("%d",&a[i]);
		}
		d[1]=a[1];
		for(int i=2;i<=k;i++){
			scanf("%d",&d[i]);	
		}
		dp[0]=0;
		dp[1]=a[1];
		for(int i=2;i<=k;i++){
			dp[i]=min(dp[i-1]+a[i],dp[i-2]+d[i]);
		}
		int hh=dp[k]/3600+8;
		int mm=(dp[k]%3600)/60;
		int ss=(dp[k]%3600)%60;
		char noon='a';
		if(hh>12){
			noon='p';
			hh-=4;
		}
		int one=hh/10;
		int two=hh%10;
		int thr=mm/10;
		int fou=mm%10;
		int fiv=ss/10;
		int six=ss%10;
		printf("%d%d:%d%d:%d%d %cm
",one,two,thr,fou,fiv,six,noon);
	}
	return 0;
}

데이터 구조: 링크 면접 문제
01 - 복잡 도 32 점 찾기 (20 점) -- 출처: PTA

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage