2083259_wa.cc

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# define MAX 2100000000
# define min(a,b) a>b?b:a
struct node
{
	long num;
	long t;
}p[301];

int n;
long min;

void solve()
{
	int i, j;
	long tmp, ans;

	tmp = ans = 0;
	for(i = n-1; i > 0; i--)
	{
		tmp += p[i].t;
		ans += tmp*p[i].num;
	}
	if(ans<min)
		min = ans;
	ans = tmp = 0;
	for(i = 0; i < n-1; i++)
	{
		tmp += p[i].t;
		ans += tmp*p[i+1].num;
	}
	if(ans<min)
		min = ans;
	for(i = 1; i < n-1; i++)
	{
		tmp = ans = 0;
		for(j = 0; j < i; j++)
		{
			tmp += p[j].t;
			ans += tmp*p[j+1].num;
		}
		tmp *= 2;
		for(j = n-1; j > i; j--)
		{
			tmp += p[j].t;
			ans += tmp*p[j].num;
		}
		if(ans<min)
			min = ans;
		tmp = ans = 0;
		for(j = n-1; j > i; j--)
		{
			tmp += p[j].t;
			ans += tmp*p[j].num;
		}
		tmp *= 2;
		for(j = 0; j < i; j++)
		{
			tmp += p[j].t;
			ans += tmp*p[j+1].num;
		}		
		if(ans<min)
			min = ans;
	}
	printf("%ld\n",min);
}

void input()
{
	int i;

	while(scanf("%d",&n)==1&&n)
	{
		if(n==1)
		{
			long a, b;
			scanf("%ld%ld",&a,&b);
			printf("0\n");
			continue;
		}
		if(n==2)
		{
			long a, b, c, d;
			scanf("%ld%ld%ld%ld",&a,&b,&c,&d);
			printf("%ld\n",c*(min(b,d)));
			continue;
		}
		min = MAX;
		for(i = 0; i < n; i++)
			scanf("%d%d",&p[i].num,&p[i].t);
		solve();
	}
}

int main()
{
	input();
	return 1;
}