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

一次水过了。。。。耗时较长。。。

Posted by lgeecn at 2011-09-24 17:47:34 on Problem 1179
#include<cstdio>
#include<vector>
#include<cctype>
#include<climits>
#include<algorithm>

long long va[120]={},dpn[110][110],dpx[110][110],ans[120]={};
int vch[120]={};

template<typename Ty>
inline const Ty &min(const Ty &a,const Ty &b)
{
	return a<b?a:b;
}

template<typename Ty>
inline const Ty &max(const Ty &a,const Ty &b)
{
	return a>b?a:b;
}

int main()
{
//	freopen("01179.in","r",stdin);
//	freopen("01179.out","w",stdout);
	unsigned long n;
	fscanf(stdin,"%u",&n);
	for(unsigned long i(1);i<=n;++i)
	{
		while(isspace(vch[i]=fgetc(stdin)));
		vch[i+n]=vch[i];
		fscanf(stdin,"%I64d",&va[i]);
		va[i+n]=va[i];
	}
	long long px(LLONG_MIN);
	for(unsigned long i(1);i<=n;++i)
	{
		for(unsigned long j(i),e(i+n);j!=e;++j)
		{
			for(unsigned long k(i);k!=e;++k)
			{
				dpn[j][k]=LONG_MAX;
				dpx[j][k]=LONG_MIN;
			}
			dpn[j][j]=dpx[j][j]=va[j];
		}
		for(unsigned long k(i),e(i+n);k!=e;++k)
		{
			for(unsigned long j(k-1),e1(k<n?0:k-n);e1<j;--j)
			{
				long long &mx(dpx[j][k]),&mn(dpn[j][k]);
				for(unsigned long l(j);l<k;++l)
				{
					switch(vch[l+1])
					{
						case 't':
							mx=max(mx,dpx[j][l]+dpx[l+1][k]);
							mn=min(mn,dpn[j][l]+dpn[l+1][k]);
						break;
						case 'x':
							mn=min(mn,
								min(dpx[j][l]*dpn[l+1][k],
								min(dpn[j][l]*dpx[l+1][k],
									dpn[j][l]*dpn[l+1][k])));
							mx=max(mx,
								max(dpx[j][l]*dpx[l+1][k],
									dpn[j][l]*dpn[l+1][k]));
					}
				}
			}
		}
		if(px<(ans[i]=dpx[i][i+n-1]))
			px=ans[i];
	}
	fprintf(stdout,"%I64d\n",px);
	for(unsigned long i(1);i<=n;++i)
		if(px==ans[i])
			fprintf(stdout,"%u ",i);
	fputc('\n',stdout);
	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