洛谷 P1430 序列取数

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