Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴java代码。DP,O(n^2)

Posted by haqishen at 2015-01-05 09:54:57 on Problem 3666
//递推公式百度一下就有很多
//虽然据说数据很弱,只要做单调上升就能AC
//但是原则上应该
//上升和下降分别做,然后取最小值 

import java.util.*;
public class Main{

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		ArrayList<Long> al = new ArrayList<Long>();
		
		int N = s.nextInt();
		long num[] = new long[N];
		for(int i = 0; i < N; i++){
			num[i] = s.nextLong();
			if(!al.contains(num[i])){
				al.add(num[i]);
			}
		}
		
		int sz = al.size();
		long snum[] = new long[sz];
		for(int i = 0; i < sz; i++)
			snum[i] = al.get(i);
		Arrays.sort(snum);		
		
		long[][] dp = new long[2][N];
		
		for(int S = 0; S < 2; S++){
			for(int i = 0; i < N; i++){
				int n;
				if(S == 0) n = i;
				else n = N-i-1;
				
				long min = dp[S][0];
				for(int j = 0; j < sz; j++){
					min = Math.min(min, dp[S][j]);
					dp[S][j] = min + Math.abs(num[n] - snum[j]);
					if(dp[S][j] == 0) break;
//					System.out.print(dp[S][j]+"	");
				}
//				System.out.println();
			}			
//			System.out.println();
		}
		
		long min = 1000000001;
		for(int j = 0; j < sz; j++){
			min = Math.min(min, Math.min(dp[0][j], dp[1][j]));			
		}
		System.out.println(min);
	}

}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator