daily pastebin goal
8%
SHARE
TWEET

Untitled

a guest May 30th, 2012 541 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top