Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2017
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <fstream>
  6. using namespace std;
  7.  
  8. int main()
  9. {
  10.    
  11.     ifstream fin;
  12.     ofstream fout;
  13.    
  14.     fin.open("input.txt");
  15.     fout.open("output.txt");
  16.    
  17.     int n;
  18.     fin >> n;
  19.    
  20.     vector<int> nums (n);
  21.     vector<int> dp(n);
  22.     vector<int> parent(n);
  23.     vector<int> result;
  24.    
  25.     for(auto&& num : nums)
  26.         fin >> num;
  27.    
  28.     for(int i = 0; i < n; i++)
  29.     {
  30.         dp[i] = 1;
  31.         parent[i] = -1;
  32.         for(int j = 0; j < i; j++)
  33.             if(nums[i] % nums[j] == 0)
  34.             {
  35.                 if(dp[j] + 1 > dp[i]){
  36.                     dp[i] = dp[j] + 1;
  37.                     parent[i] = j;
  38.                 }
  39.             }
  40.     }
  41.     int ans = dp[0], ind = 0;
  42.     for (int i = 0; i < n; i++)
  43.     {
  44.         if (dp[i] > ans) {
  45.             ans = dp[i];
  46.             ind = i;
  47.         }
  48.     }
  49.  
  50.     while(ind != -1)
  51.     {
  52.         result.push_back(ind + 1);
  53.         ind = parent[ind];
  54.     }
  55.    
  56.     fout << ans << endl;
  57.     reverse(result.begin(), result.end());
  58.     for(int i = 0; i < result.size(); i++)
  59.         fout << result[i] << " ";
  60.     fin.close();
  61.     fout.close();
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement