Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <string>
- #include <map>
- #include <queue>
- #include <cmath>
- using namespace std;
- typedef long long li;
- typedef pair<int, int> pii;
- vector<int> dp;
- vector<vector<int> > g;
- int getz(int x) {
- if (dp[x] != -1) {
- printf("\tЗначение для вершины %d вычисленои равно %d, выходим из рекурсии\n", x, dp[x]);
- return dp[x];
- }
- if (x == 0)
- return dp[x] = 1;
- dp[x] = 1;
- for (int i = 0; i < g[x].size(); i++) {
- int to = g[x][i];
- printf("\tЗначение %d на текущем шаге: %d\n", x, dp[x]);
- printf("\tПытаемся обновить ответ для %d вершины\n", x);
- printf("\tПереходим в соседа № %d\n", to);
- dp[x] = max(dp[x], getz(to) + 1);
- }
- return dp[x];
- }
- int main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int n, d;
- cin >> n >> d;
- vector<int> arr(n);
- dp.resize(n, -1);
- g.resize(n, vector<int>());
- for (int i = 0; i < n; i++) {
- cin >> arr[i];
- }
- for (int i = n - 1; i >= 0; --i) {
- cout << "Вершина №: " << i << " Соседи: ";
- for (int j = i - 1; j >= 0; --j) {
- if (abs(arr[i] - arr[j]) <= d) {
- g[i].push_back(j);
- cout << j << " ";
- }
- }
- cout << endl;
- }
- int maxx = 0;
- for (int i = 0; i < n; i++) {
- printf("Запускаем динамику с %d вершины \n", i);
- maxx = max(getz(i), maxx);
- printf("Значение динамики для %d вершины, после прохода: %d\n", i, dp[i]);
- }
- cout << "Ответ: " << maxx << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement