[submission:296009471][problem:1420C1]Hey Codeforces army..↵
----------------------↵
↵
I am stuck in this problem 1420 C1—: Pokemon Army (Easy version)↵
↵
Approach :↵
for every index i , i either pick the element and afterwards based on the previous index i add it or substract else i do not pick the element.↵
Here is my solution:↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
long long int call(vector<vector<long long int>> &dp,vector<long long int> arr,long long int idx, long long int state,long long int n){↵
if(idx>n) return 0;↵
if(dp[idx][state]!=-1) return dp[idx][state];↵
↵
int a=0, b = call(dp,arr,idx+1,state,n);↵
if(state ==1){↵
a = arr[idx];↵
}else{↵
a= -arr[idx];↵
}↵
a += call(dp,arr,idx+1,!state,n);↵
return dp[idx][state] = max(a,b);↵
}↵
int main(){↵
int t;↵
cin>>t;↵
for(int i=0;i<t;i++){↵
long long int n,q;↵
cin>>n>>q;↵
vector<long long int> arr(n+1,0);↵
for(int j=0;j<n;j++) cin>>arr[j];↵
vector<vector<long long int>> dp(n+1,vector<long long int>(2,-1));↵
long long int ans = call(dp,arr,0,1,n);↵
cout<<ans<<endl;↵
↵
}↵
return 0;↵
}
----------------------↵
↵
I am stuck in this problem 1420 C1
↵
Approach :↵
for every index i , i either pick the element and afterwards based on the previous index i add it or sub
Here is my solution:↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
long long int call(vector<vector<long long int>> &dp,vector<long long int> arr,long long int idx, long long int state,long long int n){↵
if(idx>n) return 0;↵
if(dp[idx][state]!=-1) return dp[idx][state];↵
↵
int a=0, b = call(dp,arr,idx+1,state,n);↵
if(state ==1){↵
a = arr[idx];↵
}else{↵
a= -arr[idx];↵
}↵
a += call(dp,arr,idx+1,!state,n);↵
return dp[idx][state] = max(a,b);↵
}↵
int main(){↵
int t;↵
cin>>t;↵
for(int i=0;i<t;i++){↵
long long int n,q;↵
cin>>n>>q;↵
vector<long long int> arr(n+1,0);↵
for(int j=0;j<n;j++) cin>>arr[j];↵
vector<vector<long long int>> dp(n+1,vector<long long int>(2,-1));↵
long long int ans = call(dp,arr,0,1,n);↵
cout<<ans<<endl;↵
↵
}↵
return 0;↵
}
