【河南第十届省赛-D】年终奖金
2024-10-21 09:36:26
题目描述
***公司承接了N个项目需要年底完成,每个项目有一定的难度系数。由于项目太多了,需要招聘大量的技术人员。要求每个技术人员至少完成K个项目。
考虑到有些项目之间相似性以及项目的难易程度,为了避免某些员工只挑选轻松项目,CEO提出了一个奖励机制,当技术人员完成分配给他的任务后,年终可以得到一笔奖金,其得到的酬金将是C + (Tmax–Tmin)2。其中,Tmax表示所做项目的最大的难度系数,Tmin是难度系数的最小值。
你能否计算一下,为了完成所有项目,***公司年终至少需要支付多少酬金?
输入
输入有多组测试数据。对每组测试数据:
第一行: N K C (1<=N,K<=100 1<=C<=5000 )
第二行 N个正整数分别描述N个项目的难度系数。(1<=难度系数<=10000)
输出
对每组测试数据:输出占一行,一个整数。即,***公司年终至少需要支付的酬金数。
样例输入
2 1 1
2 4
10 2 3
1 4 10 3 10 1 8 3 8 3
样例输出
2
13
提示
第一组测试数据,如果一个人完成,酬金为1 + (4–2)2 = 5;如果分给两个人去完成,收费为1 + 1 = 2。
区间dp,类似整数划分4→传送门,k > n的情况不予考虑,注意不要漏掉只有一个人完成所有任务的情况。
#include <bits/stdc++.h>
using namespace std;
const int N = ;
int dp[N], a[N];
int main()
{
int c, k, n, i, j;
while(~scanf("%d%d%d", &n, &k, &c))
{
for(i = ; i <= n; i++)
{
scanf("%d", &a[i]);
}
sort(a+, a++n);
for(i = k; i <= n; i++)
dp[i] = c+(a[i]-a[])*(a[i]-a[]);
for(i = k; i <= n; i++)
for(j = k; j+k<=i; j++)
{
dp[i] = min(dp[i], dp[j]+c+(a[i]-a[j+])*(a[i]-a[j+]));
}
cout<<dp[n]<<endl;
}
return ;
}
最新文章
- ios滑动手势全屏(这段代码实现了下一级控制器滑到上一级控制器)
- 每天一个linux命令(1):more命令
- PHPCMS二次开发教程(转)
- 使用java远程调试技术监控代码运行
- js模板引擎实现原理
- javascript 函数声明问题
- Spring Boot 入门
- 2016年9月3日 文成小盆友python-num18 - django进阶一
- 【iOS】UIDynamicAnimator动画
- java Socket多线程聊天程序
- Delphi中使用ISuperObject解析Json数据
- XFire+Spring构建Web Service经验总结
- HTTP协议初步解析
- Windows下安装RabbitMQ报错:unable to perform an operation on node时的解决方案
- GC ROOT
- Java中关于string的些许问题及解析
- JAVA项目中常用的异常处理情况总结
- spring boot 整合 shiro
- lucene学习教程
- web应用1