Name: Motherfuckers 2012-04-17 10:48
Hello there, i saw this problem somewhere, can you help me with this?
On people's demand ADZEN has decided to remove some of the billboards in such a way that there are no more than K billboards standing together in any part of the road.
You may assume the MG Road to be a straight line with N billboards.Initially there is no gap between any two adjecent billboards.
ADZEN's primary income comes from these billboards so the billboard removing process has to be done in such a way that the billboards remaining at end should give maximum possible profit among all possible final configurations.Total profit of a configuration is the sum of the profit values of all billboards present in that configuration.
Given N,K and the profit value of each of the N billboards, output the maximum profit that can be obtained from the remaining billboards under the conditions given.
Input description
Ist line contain two space seperated integers N and K. Then follow N lines describing the profit value of each billboard i.e ith line contains the profit value of ith billboard.
Sample Input
6 2
1
2
3
1
6
10
Sample Output
21
Explanation
In given input there are 6 billboards and after the process no more than 2 should be together.
So remove 1st and 4th billboards giving a configuration _ 2 3 _ 6 10 having a profit of 21. No other configuration has a profit more than 21.So the answer is 21.
my code is as follows;
#include<iostream>
using namespace std;
void siralama(int *n , int r)
{
int temp;
for(int i = 0; i < r; i++)
{
for(int j = 0; j < r - 1; j++)
{
if( n[j] > n[j+1])
{
temp = n[j];
n[j] = n[j+1];
n[j+1] = temp;
}
}
}
}
int main()
{
int *n;
int N;
int K;
cin>>N>>K;
n = new int [N];
int sum = 0;
for(int i = 0; i < N ; i++)
{
cin>>n[i];
}
siralama(n,N);
if( K > N)
{
for(int i = 0; i < N ; i++)
sum = sum + n[i];
cout<<sum;
return 0;
}
int x = N;
int count = 0;
while( x > K)
{
x = x - K;
count++;
}
for(int i = count; i < N ; i++)
{
sum = sum + n[i];
}
cout<<sum;
return 0;
}
On people's demand ADZEN has decided to remove some of the billboards in such a way that there are no more than K billboards standing together in any part of the road.
You may assume the MG Road to be a straight line with N billboards.Initially there is no gap between any two adjecent billboards.
ADZEN's primary income comes from these billboards so the billboard removing process has to be done in such a way that the billboards remaining at end should give maximum possible profit among all possible final configurations.Total profit of a configuration is the sum of the profit values of all billboards present in that configuration.
Given N,K and the profit value of each of the N billboards, output the maximum profit that can be obtained from the remaining billboards under the conditions given.
Input description
Ist line contain two space seperated integers N and K. Then follow N lines describing the profit value of each billboard i.e ith line contains the profit value of ith billboard.
Sample Input
6 2
1
2
3
1
6
10
Sample Output
21
Explanation
In given input there are 6 billboards and after the process no more than 2 should be together.
So remove 1st and 4th billboards giving a configuration _ 2 3 _ 6 10 having a profit of 21. No other configuration has a profit more than 21.So the answer is 21.
my code is as follows;
#include<iostream>
using namespace std;
void siralama(int *n , int r)
{
int temp;
for(int i = 0; i < r; i++)
{
for(int j = 0; j < r - 1; j++)
{
if( n[j] > n[j+1])
{
temp = n[j];
n[j] = n[j+1];
n[j+1] = temp;
}
}
}
}
int main()
{
int *n;
int N;
int K;
cin>>N>>K;
n = new int [N];
int sum = 0;
for(int i = 0; i < N ; i++)
{
cin>>n[i];
}
siralama(n,N);
if( K > N)
{
for(int i = 0; i < N ; i++)
sum = sum + n[i];
cout<<sum;
return 0;
}
int x = N;
int count = 0;
while( x > K)
{
x = x - K;
count++;
}
for(int i = count; i < N ; i++)
{
sum = sum + n[i];
}
cout<<sum;
return 0;
}