Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int n,z;
- int a[1000];
- int dp[1000][1000];
- int ans;
- void sort(){
- for(int i = 1; i<=n; i++){
- for(int j = i+1; j<=n; j++){
- if(a[i] > a[j])
- swap(a[i],a[j]);
- }
- }
- }
- int solve(){
- //overflowing only ith pot at last
- for(int i=1; i<=n; i++)
- dp[i][1]=a[i]*(n-i+1);
- for(int i=n; i>0; i--)
- for(int j=2; j<=z; j++)
- for(int k=i+1; k<=n; k++)
- dp[i][j] = min(dp[i][j], dp[k][j-1]) + (k-i)*a[i];
- for(int i=1; i<=n; i++){
- ans=min(ans,dp[i][z]);
- }
- return ans;
- }
- int main() {
- int t;
- cin>>t;
- while(t--){
- cin>>n>>z;
- for(int i=1; i<=n; i++)
- cin>>a[i];
- sort();
- for(int i=0; i<1000; i++){
- for(int j=0; j<1000; j++){
- dp[i][j]=100000000;
- }
- }
- ans=9999999;
- cout<<solve()<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement