poj 2231Moo Volume

Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 20699
 
Accepted: 6249
Description
Farmer John has received a noise complaint from his neighbor, Farmer Bob, stating that his cows are making too much noise. 
FJ's N cows (1 <= N <= 10,000) all graze at various locations on a long one-dimensional pasture. The cows are very chatty animals. Every pair of cows simultaneously carries on a conversation (so every cow is simultaneously MOOing at all of the N-1 other cows). When cow i MOOs at cow j, the volume of this MOO must be equal to the distance between i and j, in order for j to be able to hear the MOO at all. Please help FJ compute the total volume of sound being generated by all N*(N-1) simultaneous MOOing sessions.
Input
* Line 1: N 
* Lines 2..N+1: The location of each cow (in the range 0..1,000,000,000).
Output
There are five cows at locations 1, 5, 3, 2, and 4.
Sample Input

5
1
5
3
2
4

Sample Output

40

Hint
INPUT DETAILS: 
There are five cows at locations 1, 5, 3, 2, and 4. 
OUTPUT DETAILS: 
Cow at 1 contributes 1+2+3+4=10, cow at 5 contributes 4+3+2+1=10, cow at 3 contributes 2+1+1+2=6, cow at 2 contributes 1+1+2+3=7, and cow at 4 contributes 3+2+1+1=7. The total volume is (10+10+6+7+7) = 40.
문제풀이 사고방식: 본 문제는 임의의 두 수의 차이의 합을 요구한다.만약 직접 두 층의 순환이 틀림없이 시간을 초과할 것이다. 여기서 동태 기획의 사상을 이용하여 해답을 구할 수 있다.
우선 우리는 이 수를 작은 것부터 큰 것까지 순서를 정할 것이다. 우리는 dp[i]를 첫 번째 i개수와 전 i-1개의 수차의 합이라고 가정하면 우리는 추이 공식을 유도할 수 있다.
dp[i] = dp[i-1]+(i-1)*(a[i] - a[i-1])..마지막으로 dp[i]를 모두 합치면 2를 곱해야 한다는 것을 기억해라. 양방향이기 때문에 dp[i]는 단방향일 뿐이다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 10010;
int n;
__int64 dp[maxn],a[maxn];

int cmp(__int64 a,__int64 b)
{
	return a < b;
}

int main()
{	
	while(scanf("%d",&n)!=EOF)
	{
		for(int i = 1; i <= n; i++)
			scanf("%I64d",&a[i]);
		sort(a+1,a+n+1,cmp);
		for(int i = 1; i <= n; i++)
		{
			dp[i] = dp[i-1]+(i-1)*(a[i]-a[i-1]);
		}
		__int64 sum = 0;
		for(int i = 1; i <= n; i++)
			sum += dp[i];
		printf("%I64d
",sum<<1);
	}
	return 0;
}