欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷 P1430 序列取数

程序员文章站 2022-06-16 22:26:23
如果按照http://www.cnblogs.com/hehe54321/p/loj-1031.html的$O(n^3)$做法去做的话是会T掉的,但是实际上那个做法有优化的空间。 所有操作可以分解为由两步组成的操作:第一步是在数列的某一端取一个数并加到自己的得分上,第二步是把下一步操作的权利给自己或 ......

如果按照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 }