Spiders

This message was edited 1 time. Last update was at 01/12/2018 22:11:25

http://mendo.mk/Task.do?id=508

Ne razbiram zosto e gresen kodov.

dp[s][k][i] e maksimalniot broj na topki sto moze da se fatat ako sme vo s-tata sekunda, mozeme da se dvizime uste k pati i vo ovaa sekunda sme na i-tata pozicija.

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
template <class Key, class Compare = less<Key>> // find_by_order, order_of_key
using Tree = tree<Key, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;

int N, K, S;
int t[1001];
int dp[1001][1001][11];

void _SOLVE_() {
  int T;
  cin >> T;
  while (T--) {
    cin >> N >> K >> S;
    for (int i = 1; i <= S; ++i)
      cin >> t[i];
    memset(dp, -1, sizeof(dp));
    dp[0][K][1] = 0;
    for (int s = 1; s <= S; ++s) {
      for (int k = 0; k <= K; ++k) {
        for (int i = 1; i <= N; ++i) {
          dp[s][k][i] = dp[s-1][k][i]; //ako prethodnata sekunda stoevme ovde
          if (k > 0 && k < K) {
            if (i > 1)
              dp[s][k][i] = max(dp[s][k][i], dp[s-1][k+1][i-1]); //ako prethodnata sekunda bevme edna pozicija levo od ovde
            if (i < N)
              dp[s][k][i] = max(dp[s][k][i], dp[s-1][k+1][i+1]); //ako prethodnata sekunda bevme edna pocizija desno od ovde
          }
          if (dp[s][k][i] != -1 && t[s] == i) //mozno e da sme ovde i topkata vo ovaa sekunda pagja kade sto sme
            dp[s][k][i] += 1;
        }
      }
    }
    int ans = 0;
    for (int k = 0; k <= K; ++k)
      for (int i = 1; i <= N; ++i)
        ans = max(ans, dp[S][k][i]);
    cout << ans << endl;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  #ifdef _DEBUG
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  #endif
  _SOLVE_();
}

EDIT
Go smeniv redot (k > 0 && k < K) i tocno e sega.

VlatkoSh wrote:Go smeniv redot (k > 0 && k < K) i tocno e sega.