From 24b47b00ac5acbe36ef8c7e757a1ef97af99415a Mon Sep 17 00:00:00 2001
From: Santo Cariotti <dcariotti24@gmail.com>
Date: Sat, 18 Apr 2020 13:47:24 +0200
Subject: feat: cc 17/04/2020 tastevin

---
 I_anno/Programmazione_2/tastevin.cpp       | 47 +++++----------------
 I_anno/Programmazione_2/tastevin_paths.cpp | 67 ++++++++++++++++++++++++++++++
 2 files changed, 77 insertions(+), 37 deletions(-)
 create mode 100644 I_anno/Programmazione_2/tastevin_paths.cpp

(limited to 'I_anno/Programmazione_2')

diff --git a/I_anno/Programmazione_2/tastevin.cpp b/I_anno/Programmazione_2/tastevin.cpp
index fcd13c5..301ebcf 100644
--- a/I_anno/Programmazione_2/tastevin.cpp
+++ b/I_anno/Programmazione_2/tastevin.cpp
@@ -1,6 +1,7 @@
 #include<iostream>
 #include<fstream>
 #include<vector>
+#include<algorithm>
 
 using namespace std;
 
@@ -11,52 +12,24 @@ int main() {
     for(int ts = 0; ts < 100; ++ts) {
         int N;
         in >> N;
-        vector<int> arr;
-        int e;
+        vector<int> arr(N);
         for(int i = 0; i < N; ++i) {
-            in >> e;
-            arr.push_back(e);
+            in >> arr.at(i);
         }
 
-        int max_value{};
-        int value;
+        vector<int> paths(N, 1);
 
-        for(int i = 0; i < N; ++i) {
-            vector<int> tmp;
-            tmp.push_back(i);
-            value = arr[i];
+        for(int i = N-2; i >= 0; --i) {
+            int mx = 0;
             for(int j = i+2; j < N; ++j) {
-                if(arr[j] >= value) {
-                    tmp.push_back(j);
-                    value = arr[j];
-                    ++j;
-                }
-            }
-            while(!tmp.empty()) {
-                if(tmp.size() > max_value) {
-                    for(auto const&i : tmp) {
-                        cout << i << ' ';
-                    }
-                    cout << endl;
-                    max_value = tmp.size();
-                }
-                int k = tmp.back();
-                tmp.pop_back();
-                if(tmp.size() > 0)
-                    value = arr[tmp.back()];
-                else
-                    value = arr[k];
-                for(int j = k+1; j < N; ++j) {
-                    if(arr[j] >= value) {
-                        value = arr[j];
-                        tmp.push_back(j);
-                        ++j;
-                    }
+                if(mx < paths[j] && arr[j] >= arr[i]) {
+                    mx = paths[j];
                 }
             }
+            paths[i] += mx;
         }
 
-        out << max_value << '\n';
+        out << *max_element(begin(paths), end(paths)) << '\n';
     }
 
     in.close();
diff --git a/I_anno/Programmazione_2/tastevin_paths.cpp b/I_anno/Programmazione_2/tastevin_paths.cpp
new file mode 100644
index 0000000..eb7da54
--- /dev/null
+++ b/I_anno/Programmazione_2/tastevin_paths.cpp
@@ -0,0 +1,67 @@
+// It prints all possible paths
+
+#include<iostream>
+#include<fstream>
+#include<vector>
+
+using namespace std;
+
+int main() {
+    ifstream in("input.txt");
+    ofstream out("output.txt");
+
+    for(int ts = 0; ts < 100; ++ts) {
+        int N;
+        in >> N;
+        vector<int> arr;
+        int e;
+        for(int i = 0; i < N; ++i) {
+            in >> e;
+            arr.push_back(e);
+        }
+
+        int max_value{};
+        int value;
+
+        for(int i = 0; i < N; ++i) {
+            vector<int> tmp;
+            tmp.push_back(i);
+            value = arr[i];
+            for(int j = i+2; j < N; ++j) {
+                if(arr[j] >= value) {
+                    tmp.push_back(j);
+                    value = arr[j];
+                    ++j;
+                }
+            }
+            while(!tmp.empty()) {
+                if(tmp.size() > max_value) {
+                    for(auto const&i : tmp) {
+                        cout << i << ' ';
+                    }
+                    cout << endl;
+                    max_value = tmp.size();
+                }
+                int k = tmp.back();
+                tmp.pop_back();
+                if(tmp.size() > 0)
+                    value = arr[tmp.back()];
+                else
+                    value = arr[k];
+                for(int j = k+1; j < N; ++j) {
+                    if(arr[j] >= value) {
+                        value = arr[j];
+                        tmp.push_back(j);
+                        ++j;
+                    }
+                }
+            }
+        }
+
+        out << max_value << '\n';
+    }
+
+    in.close();
+    out.close();
+    return 0;
+}
-- 
cgit v1.2.3-18-g5258