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