Hackrank Equal DP
Christy is interning at HackerRank. One day she has to distribute some chocolates to her colleagues. She is biased towards her friends and may have distributed the chocolates unequally. One of the program managers gets to know this and orders Christy to make sure everyone gets equal number of chocolates.
But to make things difficult for the intern, she is ordered to equalize the number of chocolates for every colleague in the following manner,
For every operation, she can choose one of her colleagues and can do one of the three things.
- She can give one chocolate to every colleague other than chosen one.
- She can give two chocolates to every colleague other than chosen one.
- She can give five chocolates to every colleague other than chosen one.
Calculate minimum number of such operations needed to ensure that every colleague has the same number of chocolates.
Input Format
First line contains an integer denoting the number of testcases. testcases follow.
Each testcase has lines. First line of each testcase contains an integer denoting the number of colleagues. Second line contains N space separated integers denoting the current number of chocolates each colleague has.
Constraints
Number of initial chocolates each colleague has <
Output Format
lines, each containing the minimum number of operations needed to make sure all colleagues have the same number of chocolates.
Sample Input
1
4
2 2 3 7
Sample Output
2
Explanation
1st operation: Christy increases all elements by 1 except 3rd one
2 2 3 7 -> 3 3 3 8
2nd operation: Christy increases all element by 5 except last one
3 3 3 8 -> 8 8 8 8
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double Pi = acos(-1.0);
const int N = 6e3+, M = 1e3+, mod = ,inf = 2e9; int dp[N][N],a[];
int main() {
for(int i = ;i <= ; ++i)
for(int j = ; j <= ; ++j) dp[i][j] = inf; for(int i = ; i <= ; ++i) {
dp[i][i] = ;
for(int j = ; j < i; ++j) {
if(i->=j)
dp[i][j] = min(dp[i-][j]+,dp[i][j]);
if(i->=j)
dp[i][j] = min(dp[i-][j]+,dp[i][j]);
if(i->=j)
dp[i][j] = min(dp[i-][j]+,dp[i][j]);
}
}
int T,n;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
int mi = inf;
for(int i = ; i <= n; ++i) scanf("%d",&a[i]),mi = min(mi,a[i]+);
int ans = ;
for(int i = ; i <= n; ++i) {
ans += dp[a[i]+][mi];
}
for(int i = ; i <= mi; ++i) {
int sum = ;
for(int j = ; j <= n; ++j) {
sum += dp[a[j]+][i];
}
ans = min(ans,sum);
}
printf("%d\n",ans);
}
return ;
}
最新文章
- 关于Block的简单使用
- 迷你MVVM框架 avalonjs1.5 入门教程
- DOS命令批量重命名文件配合Excel 操作备忘
- don&#39;t forget the bigger picture
- 支付SDK的安全问题——隐式意图可导致钓鱼攻击
- /bin/dd if=/path/to/source-file of=/path/to/backup-file
- 监控mysql主从同步状态脚本
- c/c++小知识
- JSONObject 包的依赖
- PAT-乙级-1002. 写出这个数 (20)
- 关于Optimizer_index_cost_adj参数的设置
- Codeforces Round #277 (Div. 2) 题解
- epoll的ET和LT两种模式对比及注意事项
- springboot--springboot+mybatis多数据源最简解决方案
- C#,一份超简单的数据库帮助类,SqlHelp
- SQLServer之创建存储过程
- nginx域名跳转到www下
- poj 3687 Labeling Balls(拓补排序)
- P1135 奇怪的电梯 dp
- 用PHP山寨一款软件