Time Limit: 1 second Memory Limit: 32 MB
【问题描述】
一位管理项目的经理想要确定每个月需要的工人，他知道每月所需的最少工人数。当他雇佣或解雇一个工人时，会有一些额外支出。一旦一个工人被雇佣，即使他不工作，他也将得到工资。这位经理知道雇佣一个工人的费用，解雇一个工人的费用和一个工人的工资。现他在考虑一个问题：为了把项目的费用控制在最低，他将每月雇佣或解雇多少个工人。【输入格式】
共三行。第一行为月数n（不超过12）。第二行含雇佣一个工人的费用、一个工人的工资和解雇一个工人的费用（≤100）。第三行含n个数，分别表示每月最少需要的工人数（≤1000）。每个数据之间有一个空格隔开。【输出格式】
仅一行，表示项目的最小总费用。【输入样例】
34 5 610 9 11【输出样例】
199【题目链接】:http://noi.qz5z.com/viewtask.asp?id=a601
【题意】
【题解】
/* 设f[i][j]表示第i个月有j个工人的最小花费; memset(f,255,sizeof f); f[1][mi[1]] = h*mi[1]+mi[1]*s; rep1(i,1,n-1) rep1(j,mi[i],1000) if (f[i][j]!=-1) { if (j<=mi[i+1]) { if (f[i+1][mi[i+1]]==-1) f[i+1][mi[i+1]] = f[i][j]+(mi[i+1]-j)*h+mi[i+1]*s; else f[i+1][mi[i+1]] = min(f[i+1][mi[i+1]],f[i][j]+(mi[i+1]-j)*h+mi[i+1]*s); } else { //j>mi[i+1]; rep1(k,mi[i+1],j) { if (f[i+1][k] ==-1) f[i+1][k] = f[i][j]+f*(j-k)+k*s; else f[i+1][k] = min(f[i+1][k],f[i][j]+f*(j-k)+k*s); } } } 最后在f[n][mi[n]..1000]里面找答案;*/【完整代码】
#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%lld",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int N = 15;int n,h,s,f;int mi[N],dp[N][2000];int main(){ //freopen("F://rush.txt","r",stdin); rei(n); rei(h),rei(s),rei(f); rep1(i,1,n) rei(mi[i]); memset(dp,255,sizeof dp); dp[1][mi[1]] = h*mi[1]+mi[1]*s; rep1(i,1,n-1) rep1(j,mi[i],1000) if (dp[i][j]!=-1) { if (j<=mi[i+1]) { if (dp[i+1][mi[i+1]]==-1) dp[i+1][mi[i+1]] = dp[i][j]+(mi[i+1]-j)*h+mi[i+1]*s; else dp[i+1][mi[i+1]] = min(dp[i+1][mi[i+1]],dp[i][j]+(mi[i+1]-j)*h+mi[i+1]*s); } else { //j>mi[i+1]; rep1(k,mi[i+1],j) { if (dp[i+1][k] ==-1) dp[i+1][k] = dp[i][j]+f*(j-k)+k*s; else dp[i+1][k] = min(dp[i+1][k],dp[i][j]+f*(j-k)+k*s); } } } int ans = 0x3f3f3f3f; rep1(i,mi[n],1000) if (dp[n][i]!=-1) ans = min(ans,dp[n][i]); PRintf("%d/n",ans); return 0;}新闻热点
疑难解答
