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

Re:公式数学推导

Posted by CSUST_14 at 2013-04-20 11:05:56 on Problem 1701
In Reply To:公式数学推导 Posted by:CSUST_14 at 2013-04-20 11:03:03
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int N =10005;
typedef __int64 LL;
LL C[N],T[N],H[N],M[N],S[N],sum[N];
LL Sum;
LL ar[N];
LL a,b;
int n;

void getsum()
{
	sum[1] = ar[1];
	for(int i=2;i<=n;i++)
		sum[i] = sum[i-1] + ar[i];

	Sum = sum[n];
}

void getTH()
{
	T[1] = b*ar[1];
	H[1] = 0;

	for(int i=2;i<=n;i++)
		T[i] = T[i-1] + b*ar[i], H[i] = H[i-1] + sum[i-1];
}
void getMS()
{
	M[n] = 0;
	S[n] = 0;

	for(int i=n-1;i>=1;i--)
		M[i] = M[i+1] + (1-a)*ar[i+1],S[i] = S[i+1] + Sum - sum[i];
}
void getczero()
{
	C[1] =  0;
	for(int i=2;i<=n;i++)
		C[1] += ar[i] * (a*(i-1) + (i-1)*(i-2)/2);
}
void getC()
{
	for(int i=2;i<=n;i++)
		C[i] = C[i-1] + T[i-1] + H[i-1] + M[i-1] -S[i-1];
}
int getMin()
{
	LL Min = C[1];
	int index = 1;
	for(int i=2;i<=n;i++)
		if(Min>C[i]) Min = C[i],index = i;
	return index;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%I64d%I64d",&n,&a,&b);

		for(int i=1;i<=n;i++)
			scanf("%I64d",&ar[i]);

		getsum();
		getTH();
		getMS();
		getczero();
		getC();
		printf("%d\n",getMin());
	}
	return 0;
}

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