洛谷 P1430 序列取数

2018-02-08 19:01:45来源:cnblogs.com作者:hehe_54321人点击

分享

如果按照http://www.cnblogs.com/hehe54321/p/loj-1031.html的$O(n^3)$做法去做的话是会T掉的,但是实际上那个做法有优化的空间。

所有操作可以分解为由两步组成的操作:第一步是在数列的某一端取一个数并加到自己的得分上,第二步是把下一步操作的权利给自己或对方。如果这次操作的前一次是对方的操作,那么在左端或右端取数没有限制;如果这次操作的前一次是自己的操作,那么必须与上一次在相同的一端操作。

令ans[l][r][0/1/2]表示l到r的子序列,上一次操作是(0->对方取)或(1->自己取左端)或(2->自己取右端),先取者的最高得分。则可以得到状态转移方程。复杂度$O(n^2)$。

(枚举状态要按照一定的顺序)

这题卡常!

 1 #pragma GCC diagnostic error "-std=c++11" 2 #pragma GCC target("avx") 3 #pragma GCC optimize(3) 4 #pragma GCC optimize("Ofast") 5 #pragma GCC optimize("inline") 6 #pragma GCC optimize("-fgcse") 7 #pragma GCC optimize("-fgcse-lm") 8 #pragma GCC optimize("-fipa-sra") 9 #pragma GCC optimize("-ftree-pre")10 #pragma GCC optimize("-ftree-vrp")11 #pragma GCC optimize("-fpeephole2")12 #pragma GCC optimize("-ffast-math")13 #pragma GCC optimize("-fsched-spec")14 #pragma GCC optimize("unroll-loops")15 #pragma GCC optimize("-falign-jumps")16 #pragma GCC optimize("-falign-loops")17 #pragma GCC optimize("-falign-labels")18 #pragma GCC optimize("-fdevirtualize")19 #pragma GCC optimize("-fcaller-saves")20 #pragma GCC optimize("-fcrossjumping")21 #pragma GCC optimize("-fthread-jumps")22 #pragma GCC optimize("-funroll-loops")23 #pragma GCC optimize("-fwhole-program")24 #pragma GCC optimize("-freorder-blocks")25 #pragma GCC optimize("-fschedule-insns")26 #pragma GCC optimize("inline-functions")27 #pragma GCC optimize("-ftree-tail-merge")28 #pragma GCC optimize("-fschedule-insns2")29 #pragma GCC optimize("-fstrict-aliasing")30 #pragma GCC optimize("-fstrict-overflow")31 #pragma GCC optimize("-falign-functions")32 #pragma GCC optimize("-fcse-skip-blocks")33 #pragma GCC optimize("-fcse-follow-jumps")34 #pragma GCC optimize("-fsched-interblock")35 #pragma GCC optimize("-fpartial-inlining")36 #pragma GCC optimize("no-stack-protector")37 #pragma GCC optimize("-freorder-functions")38 #pragma GCC optimize("-findirect-inlining")39 #pragma GCC optimize("-fhoist-adjacent-loads")40 #pragma GCC optimize("-frerun-cse-after-loop")41 #pragma GCC optimize("inline-small-functions")42 #pragma GCC optimize("-finline-small-functions")43 #pragma GCC optimize("-ftree-switch-conversion")44 #pragma GCC optimize("-foptimize-sibling-calls")45 #pragma GCC optimize("-fexpensive-optimizations")46 #pragma GCC optimize("-funsafe-loop-optimizations")47 #pragma GCC optimize("inline-functions-called-once")48 #pragma GCC optimize("-fdelete-null-pointer-checks")49 #include<cstdio>50 #include<cstring>51 #include<algorithm>52 using namespace std;53 int sum[1010],ans[1010][1010][3],a[1010],T,n;54 inline int read() {55     int x=0,f=1;char ch=getchar();56     while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}57     while(ch>='0'&&ch<='9'){x*=10;x+=(ch-'0');ch=getchar();}58     return x*f;59 }60 inline void write(int x) {61     if(x<0) putchar('-'),x=-x;62     if(x>9) write(x/10);63     putchar(x%10+'0');64 }65 int main()66 {67     register int i,l;68     int r;69     T=read();70     while(T--)71     {72         memset(ans,0,sizeof(ans));73         n=read();74         for(i=1;i<=n;++i)75             a[i]=read();76         for(i=1;i<=n;++i)77             sum[i]=sum[i-1]+a[i];78         for(i=1;i<=n;++i)79             ans[i][i][0]=ans[i][i][1]=ans[i][i][2]=a[i];80         for(i=2;i<=n;++i)81             for(l=1;l<=n-i+1;++l)82             {83                 r=l+i-1;84                 ans[l][r][0]=max(sum[r]-sum[l-1]-min(ans[l+1][r][0],ans[l][r-1][0]),max(a[l]+ans[l+1][r][1],a[r]+ans[l][r-1][2]));85                 ans[l][r][1]=max(sum[r]-sum[l-1]-ans[l+1][r][0],a[l]+ans[l+1][r][1]);86                 ans[l][r][2]=max(sum[r]-sum[l-1]-ans[l][r-1][0],a[r]+ans[l][r-1][2]);87             }88         write(ans[1][n][0]);putchar('/n');89     }90     return 0;91 }

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台