PROBLEM LINK:
Author: Shriram Chandran
Editorialist: Shriram Chandran
DIFFICULTY:
Medium
PREREQUISITES:
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;
}