Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- using namespace std;
- int n, k, S;
- int niza[1005];
- int dp[15][1005][1005];
- int rec(int i, int brnacekori, int brnacevki){
- if(i==S){
- return 0;
- }
- if(dp[brnacevki][brnacekori][i]!=-1){
- return dp[brnacevki][brnacekori][i];
- }
- int result=0;
- int topka=0;
- if(niza[i]==brnacevki){
- topka=1;
- }
- result=max(result, rec(i+1, brnacekori, brnacevki)+topka);
- if((brnacevki - 1 >= 0)and(brnacekori<k)){
- result=max(result, rec(i+1, brnacekori+1, brnacevki-1)+topka);
- }
- if((brnacevki + 1 < n )and(brnacekori<k)){
- result=max(result, rec(i+1, brnacekori+1, brnacevki+1)+topka);
- }
- dp[brnacevki][brnacekori][i]=result;
- return (result);
- }
- ///n broj na cevki
- ///k broj na dvizenja
- ///s golemina na niza
- int main()
- {
- int t;
- cin >> t;
- while(t--) {
- cin>>n>>k>>S;
- for(int i=0; i<S; i++){
- cin>>niza[i];
- niza[i]--;
- }
- for(int i=0; i<=n; i++){
- for(int j=0; j<=k; j++){
- for(int k=0; k<=S; k++){
- dp[i][j][k]=-1;
- }
- }
- }
- int r = rec(0, 0, 0);
- if(k > 0) {
- r = max(r, rec(0, 1, 1));
- }
- cout << r << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement