Advertisement
Guest User

Untitled

a guest
May 30th, 2012
755
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.50 KB | None | 0 0
  1. import java.io.*;
  2. import java.math.BigInteger;
  3. import java.util.*;
  4.  
  5. public class monotone_nv_bigint {
  6.     public static void main(String[] args) {
  7.         new monotone_nv_bigint().run();
  8.     }
  9.  
  10.     BufferedReader br;
  11.     StringTokenizer in;
  12.     PrintWriter out;
  13.  
  14.     public String nextToken() throws IOException {
  15.         while (in == null || !in.hasMoreTokens()) {
  16.             in = new StringTokenizer(br.readLine());
  17.         }
  18.         return in.nextToken();
  19.     }
  20.  
  21.     public int nextInt() throws IOException {
  22.         return Integer.parseInt(nextToken());
  23.     }
  24.  
  25.     public long nextLong() throws IOException {
  26.         return Long.parseLong(nextToken());
  27.     }
  28.  
  29.     public double nextDouble() throws IOException {
  30.         return Double.parseDouble(nextToken());
  31.     }
  32.  
  33.     int a[];
  34.  
  35.     boolean check(int pos, int cnt) throws IOException {
  36.         boolean f = true;
  37.         for (int i = pos - cnt + 1; i < pos; i++) {
  38.             if (a[i] < a[i + 1]) {
  39.                 f = false;
  40.             }
  41.         }
  42.         if (f) {
  43.             return true;
  44.         }
  45.         f = true;
  46.         for (int i = pos - cnt + 1; i < pos; i++) {
  47.             if (a[i] > a[i + 1]) {
  48.                 f = false;
  49.             }
  50.         }
  51.         return f;
  52.     }
  53.  
  54.     void solve() throws IOException {
  55.         int n = nextInt();
  56.         assert 1 <= n && n <= 50000;
  57.         a = new int[n + 1];
  58.         BigInteger dp[] = new BigInteger[4];
  59.         int parent[] = new int[n + 1];
  60.         for (int i = 0; i < n; i++) {
  61.             a[i + 1] = nextInt();
  62.             assert 0 <= a[i + 1] && a[i + 1] <= (int) 1e9;
  63.         }
  64.         dp[0] = dp[1] = BigInteger.ONE;
  65.         dp[2] = BigInteger.valueOf(2);
  66.         for (int i = 3; i <= n; i++) {
  67.             dp[3] = dp[2];
  68.             parent[i] = i - 1;
  69.             for (int j = 2; j < 4; j++) {
  70.                 if (check(i, j)) {
  71.                     BigInteger tmp = dp[3 - j].multiply(BigInteger.valueOf(j));
  72.                     if (dp[3].compareTo(tmp) < 0) {
  73.                         dp[3] = tmp;
  74.                         parent[i] = i - j;
  75.                     }
  76.                 }
  77.             }
  78.             for (int j = 0; j < 3; j++) {
  79.                 dp[j] = dp[j + 1];
  80.             }
  81.         }
  82.         //out.println(dp[3].toString());
  83.         ArrayList<Integer> ans = new ArrayList<Integer>();
  84.         int t = n;
  85.         while (t > 0) {
  86.             ans.add(t);
  87.             t = parent[t];
  88.         }
  89.         Collections.reverse(ans);
  90.         out.println(ans.size());
  91.         for (int i = 0; i < ans.size(); i++) {
  92.             out.print(ans.get(i) + ((i == ans.size() - 1) ? "\n" : " "));
  93.         }
  94.     }
  95.  
  96.     public void run() {
  97.         try {
  98.             br = new BufferedReader(new InputStreamReader(System.in));
  99.             out = new PrintWriter(System.out);
  100.             //br = new BufferedReader(new FileReader("monotone.in"));
  101.             //out = new PrintWriter("monotone.out");
  102.             solve();
  103.             out.close();
  104.         } catch (IOException e) {
  105.             e.printStackTrace();
  106.             System.exit(1);
  107.         }
  108.     }
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement