hdu1158
1311 단어 ini
분석:
i는 월수, l은 인원수,num[i]는 i월에 몇 명이 필요한지, 토탈은 최대 몇 명이 필요한지.
dp[i][l]=min(dp[i-1][k]+l*s+k>l?(k-l)*f:(l-k)*h) num[i-1]<=k<=total
ans=min(dp[마지막 달][k])num[마지막 달]<=k<=total
2012-05-17
*/
#include"stdio.h"
int min(int a,int b)
{
return a>b?b:a;
}
int main()
{
int n;
int h,s,f;
int num[15];
int i,l,j;
int total;
int dp[12][1011];
int ans;
while(scanf("%d",&n),n)
{
scanf("%d%d%d",&h,&s,&f);
total=0;
for(i=0;i<n;i++) //i 0
{
scanf("%d",&num[i]);
if(total<num[i]) total=num[i];
}
if(total==0)
{
printf("0
");
continue;
}
for(l=num[0];l<=total;l++) dp[0][l]=l*(h+s);
for(i=1;i<n;i++)
{
for(l=num[i];l<=total;l++)
{
if(num[i-1]>l) dp[i][l]=dp[i-1][num[i-1]]+l*s+(num[i-1]-l)*f;
else dp[i][l]=dp[i-1][num[i-1]]+l*s+(l-num[i-1])*h;
for(j=num[i-1]+1;j<=total;j++)
{
if(j>l) dp[i][l]=min(dp[i][l],dp[i-1][j]+l*s+(j-l)*f);
else dp[i][l]=min(dp[i][l],dp[i-1][j]+l*s+(l-j)*h);
}
}
}
ans=111111111;
for(l=num[n-1];l<=total;l++) ans=min(dp[n-1][l],ans);
printf("%d
",ans);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1017 A Mathematical Curiosity(문제 해결 보고서)바보 B원에서 전재하다 Problem Description Given two integers n and m, count the number of pairs of integers (a,b) such that 0 < a...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
