summaryrefslogtreecommitdiff
path: root/I_anno/Programmazione_2
diff options
context:
space:
mode:
authorSanto Cariotti <dcariotti24@gmail.com>2020-04-18 13:47:24 +0200
committerSanto Cariotti <dcariotti24@gmail.com>2020-04-18 13:47:24 +0200
commit24b47b00ac5acbe36ef8c7e757a1ef97af99415a (patch)
tree7548707297fb699f31467ea1fc365679525faf1b /I_anno/Programmazione_2
parent6724b06992451919397e8c69caf0f912976a3a9b (diff)
feat: cc 17/04/2020 tastevin
Diffstat (limited to 'I_anno/Programmazione_2')
-rw-r--r--I_anno/Programmazione_2/tastevin.cpp47
-rw-r--r--I_anno/Programmazione_2/tastevin_paths.cpp67
2 files changed, 77 insertions, 37 deletions
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;
+}