年終獎金 - 菜鳥學院

題目描述

***公司承接了N個項目須要年末完成，每一個項目有必定的難度係數。因爲項目太多了，須要招聘大量的技術人員。要求每一個技術人員至少完成K個項目。
考慮到有些項目之間類似性以及項目的難易程度，爲了不某些員工只挑選輕鬆項目，CEO提出了一個獎勵機制，當技術人員完成分配給他的任務後，年終能夠獲得一筆獎金，其獲得的酬金將是C + (Tmax–Tmin)2。其中，Tmax表示所作項目的最大的難度係數，Tmin是難度係數的最小值。
你可否計算一下，爲了完成全部項目，***公司年終至少須要支付多少酬金？

輸入

輸入有多組測試數據。對每組測試數據：
第一行：NKC(1<=N，K<=1001<=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)² = 5；若是分給兩我的去完成，收費爲1 + 1 = 2。html

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; int main() { int n,k,c,a[10005],b[10005]; while(scanf("%d%d%d",&n,&k,&c)!=EOF){ for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); memset(b,INF,sizeof(b)); b[0]=0; for(int i=k;i<=n;i++) for(int j=1;j<=i-k+1;j++) if(j>k||j==1) b[i]=min((a[i]-a[j])*(a[i]-a[j])+c+b[j-1],b[i]); printf("%d\n",b[n]); } return 0; }