Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <vector>
- #include <algorithm>
- #include <fstream>
- using namespace std;
- int main()
- {
- ifstream fin;
- ofstream fout;
- fin.open("input.txt");
- fout.open("output.txt");
- int n;
- fin >> n;
- vector<int> nums (n);
- vector<int> dp(n);
- vector<int> parent(n);
- vector<int> result;
- for(auto&& num : nums)
- fin >> num;
- for(int i = 0; i < n; i++)
- {
- dp[i] = 1;
- parent[i] = -1;
- for(int j = 0; j < i; j++)
- if(nums[i] % nums[j] == 0)
- {
- if(dp[j] + 1 > dp[i]){
- dp[i] = dp[j] + 1;
- parent[i] = j;
- }
- }
- }
- int ans = dp[0], ind = 0;
- for (int i = 0; i < n; i++)
- {
- if (dp[i] > ans) {
- ans = dp[i];
- ind = i;
- }
- }
- while(ind != -1)
- {
- result.push_back(ind + 1);
- ind = parent[ind];
- }
- fout << ans << endl;
- reverse(result.begin(), result.end());
- for(int i = 0; i < result.size(); i++)
- fout << result[i] << " ";
- fin.close();
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement