4876828_wa.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 58 行

#include<iostream>
using namespace std;
int x[2050];
int tmax,n;
struct state
{
	int i,j,all,day;
}q[10005];
void bfs()
{
	int head=0,tail=1;
	q[0].i=0;q[0].j=n-1;
	q[0].all=0;
	q[0].day=1;
	while(head<tail)
	{
		state temp=q[head];
		while(temp.i<temp.j)
		{
			if(x[temp.i]<x[temp.j]) {temp.all+=x[temp.i]*temp.day;temp.day++;temp.i++;}
			else if(x[temp.i]>x[temp.j]) {temp.all+=x[temp.j]*temp.day;temp.day++;temp.j--;}
			else
			{
				state k;
				k.all=temp.all+x[temp.i]*temp.day;
				k.day=temp.day+1;
				k.j=temp.j;
				k.i=temp.i+1;
				q[tail++]=k;if(tail>10000) tail=0;
				k.all=temp.all+x[temp.j]*temp.day;
				k.day=temp.day+1;
				k.j=temp.j-1;
				k.i=temp.i;
				q[tail++]=k;
				if(tail>10000) tail=0;
				break;
			}
		}
		if(temp.i==temp.j)
		{
			temp.all+=temp.day*x[temp.i];
			if(temp.all>tmax)tmax=temp.all;
		}
		head++;
		if(head>10000) head=0;
	}
}
int main()
{
	int i;
	cin>>n;
	for(i=0;i<n;i++) cin>>x[i];
	int all=0;
	tmax=0;
	bfs();
	cout<<tmax;
	return 0;
}