HDU 4011 Working in Beijing 베 이 징 에서 작업 (간단 한 시 뮬 레이 션 선택 분석)
10227 단어 HDU모방 하 다우수한 것 을 고르다
Working in Beijing Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 2650 Accepted Submission(s): 1038
Problem Description Mr. M is an undergraduate student of FDU. He finds an intern position in Beijing, so that he cannot attend all the college activities. But in some conditions, he must come back to Shanghai on certain date. We can assume the important activities that Mr. M must attend are occupy a whole day. Mr. M must take flight to Shanghai before that day and leave after that day. On the other hand, Mr. M is absent in Beijing and he will lose his salary for his absent. Sometimes the cost of flight is much higher than the loss of salary, so to save the cost on the travel, Mr. M can stay in Shanghai to wait for another important date before he back to Beijing. Now, Mr. M knows all of the important date in the next year. Help him schedule his travel to optimize the cost.
Input The input contains several test cases. The first line of single integer indicates the number of test cases. For each test case, the first line contains three integers: n, a and b, denoting the number of important events, the cost of a single flight from Beijing to Shanghai or Shanghai to Beijing and the salary for a single day stay in Beijing. (1 <= n <= 100000, 1 <= a <= 1000000000, 1 <= b <=100) Next line contains n integers ti, denoting the time of the important events. You can assume the ti are in increasing order and they are different from each other. (0 <= ti <= 10000000)
Output For each test case, output a single integer indicating the minimum cost for this year.
Sample Input 2 1 10 10 5 5 10 2 5 10 15 65 70
Sample Output Case #1: 30 Case #2: 74
Source The 36th ACM/ICPC Asia Regional Shanghai Site —— Warmup
제목 해석: 제목 은 M 선생 이 베 이 징 에서 일 하 는데 매년 상하 이에 가서 회의 에 참석 해 야 한 다 는 것 이다. 두 가지 방안 이 있 는데 하 나 는 두 번 의 회의 사이 에 상하 이에 있 는 것 이다. 다른 하 나 는 한 번 의 회의 에 참가 하고 베 이 징 으로 돌아 가 는 것 이다. 그때 다시 상하 이에 가서 두 번 째 회의 에 참가 하 는 것 이다. 두 가지 중의 최저 원 가 를 분석 하고 수출 하 는 것 이다. 어쨌든 회의 일 수 는 무단결근 으로 인해 발생 한다.월급 공제, 그리고 처음 가 는 것 과 마지막 으로 떠 나 는 비행기표 값 은 고정 되 어 있 습 니 다. 내부 의 두 간격 을 분석 하면 됩 니 다.
AC 코드:
#include
using namespace std;
const int X = 100008;
long long int al[X];
long long money; //
int main()
{
int n,k=1;
cin >> n;
while (n--)
{
money = 0;
memset(al, 0, sizeof(al));
int a, b, c, i, j;
scanf("%d%d%d", &a, &b, &c);
for (i = 0; i < a; i++)
{
scanf("%d", &al[i]);
}
if (a == 1)
{
cout << "Case #"<<k++<<": "<<(2 * b + c) << endl; continue;
}
for (i = 0, j = 1; j < a; i++, j++)
{
if ((al[j] - al[i]-1) * c < 2 * b) //
{
money =money+ (al[j] - al[i]-1) * c;
}
else
{
money = money + 2 * b;
}
}
money = money + a * c + 2 * b; //
cout << "Case #" << k++ << ": "<< money << endl;
}
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에 따라 라이센스가 부여됩니다.