# SOPC012 Editorial

Author: Shriram Chandran
Editorialist: Shriram Chandran

Medium

DP.

# PROBLEM:

Given two sequences of size N, select a sequence with maximal number of distinct indices with minimum cost.

# EXPLANATION:

Note that you can always plant N different plants of either type. Thus the maximum number of types of crops you can produce is always N. Since there are N acres to grow N different crops, we grow each once, thus we choose only one, either type 1 or 2 for each crop.

Let us now solve this problem with a 2*N dp:

Consider an array dp, where dp_{i,j} is the minimum cost for the first i crops, and j=1 if the ith crop was of type 1 and j=2 if the ith crop is of type 2. Thus, dp_{1,1}=x_1 and dp_{1,2}=c(k_1+1). The transitions are clear:

• dp_{i,1}=min(dp_{i-1,1},dp_{i-1,2})+x_i
• dp_{i,2}=min(dp_{i-1,1}+c(k_i+1),dp_{i-1,2}+c)

The minimum cost is min(dp_{n,1},dp_{n,2}).

# SOLUTION:

Setter's Solution
``````#include<bits/stdc++.h>
#define ll long long
#define min(a,b) ((a<b)?a:b)

using namespace std;

void solve()
{
ll n,c;
cin>>n>>c;
ll x[n],k[n];
for(ll i=0;i<n;i++)
cin>>x[i];
for(ll i=0;i<n;i++)
cin>>k[i];
ll dp[n][2];
dp[0][0]=x[0];
dp[0][1]=c*(k[0]+1);
for(int i=1;i<n;i++)
{
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+x[i];
dp[i][1]=min(dp[i-1][0]+c*(k[i]+1),dp[i-1][1]+c);
}
cout<<n<<" "<<min(dp[n-1][0],dp[n-1][1])<<endl;
}

int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}
``````

I still donâ€™t get the reason behind printing the maximum number distinct crops one can get? It is mentioned in the problem to be N, so why the bootless mislead?

1 Like

maybe thatâ€™s what they intendedâ€¦ by adding some confusion