| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
一次水过了。。。。耗时较长。。。#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator