Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:
t1 t2 d(A) = max{ ∑ai + ∑aj | 1 <= s1 <= t1 < s2 <= t2 <= n } i=s1 j=s2 Your task is to calculate d(A).Print exactly one line for each test case. The line should contain the integer d(A).
大意：
这道题我不想翻译QAQ，而且就是翻译了也读不懂吧 o(>﹏<)o
所以直接写怎么操作：
这道题有T组数据，每组数据有一个n,表示数组的长度，接着一行输入数组。要求在数组中找两端连续的子段，且不能有重合部分，要使这两段之和最大。不能连环。数据范围：T<=30，2<=n<=50000，|数组元素| <= 10000（看得出来这是绝对值吧）。
深搜思路简析（TLE是肯定的）：
标准TLE，如果想看AC的，往下划找DP算法思路。不过建议DP新手先看一看深搜，帮助DP入门。深搜先在主函数枚举子段起点，将dfs();作为循环体，dfs函数里面要有if判断子段起点是否越界（循环那里已经控制，但后面有递归，需控制边界），要有一个bool变量判断第二段是否已分（这里有改进，可以改为int变量，可以分三段四段balabala...），如果还没分第二段，就和分第一段一样用for循环枚举起点。
代码实现（TLE）：
#include<cstdio> #include<algorithm> using namespace std; int n,ans,sum,a[50005]; bool flag; void dfs(int x) { ans=max(ans,sum); if(x<=n) { sum+=a[x]; if(!flag) { flag=1; for(int j=x+1;j<=n;j++) dfs(j); flag=0; } dfs(x+1); sum-=a[x]; } } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) dfs(i); printf("%d\n",ans); } }
DP思路简析：
刚开始想用前缀和做，可是前缀和 每次 都 要 算，重复计算太麻烦。于是想用一个二维数组f[i][j]表示从第i个元素到第j个元素的和，可是开不了那么大的数组（50000的数据范围）。所以改用两个一维数组，f[i]表示从1...i（一定包括a[i]）的最大子段和，g[i]表示从n...i+1（一定包括a[i+1]）的最大子段和，f[]可以一边输入以便处理，节约时间，g[]要单独用一个for倒序计算，最后还要一个for枚举断点。这么做会发现一个问题：两段是一定连续的，没有枚举出来所有可能的解（一定包含a[i]和a[i+1]导致）。我还想过f[]和g[]不加a[i]和a[i+1]，但是会影响递推式；在ans那里计算一下不带a[i]和a[i+1]的可能的值，再比较，只能过小部分数据。于是就又加了两个数组F[]和G[]来记录不一定加上a[i]和a[i+1]的值的最大值（如果a[i]和a[i+1]加上比不加大，即a[i]和a[i+1]为正或0），每次处理一个f[]和g[]就计算一个F[]和G[]。
代码实现：
#include<cstdio> #include<algorithm> using namespace std; int a[50001],f[50001],g[50001],F[50001],G[50001]; int main()//a[]输入的数据,f[i]指1...i(含a[i])的最大子段和,g[i]指n...i+1(含a[i+1])的最大子段和, {//F[i]指1...i(不一定含a[i])的最大子段和,G[i]指n...i+1(不一定含a[i+1])的最大子段和 int t,n,ans=-1e8;//这道题有负数，ans要尽量小，不能为0（当然INT_MIN也是可以的，不过要加头文件#include<climits>） scanf("%d",&t); while(t--) { scanf("%d %d",&n,&a[1]); F[1]=f[1]=a[1];//初始数组f[],F[] int mx=f[1];//初始mx for(int i=2;i<=n;i++) { scanf("%d",&a[i]); f[i]=max(a[i]+f[i-1],a[i]); F[i]=max(f[i],mx); mx=F[i];//滚动mx，下次循环时,mx是不加上a[i]的最大值（a[i-1]加不加倒不确定，不过并没有影响，不要被这里弄懵了） }//而这里=F[i]而不赋值为f[i]的原因是：f[i]是一定加了a[i]，F[i]则不是，F[i]根据“需要”选择加不加a[i]，所以最大 G[n]=g[n]=0;//(如果a[i]为负数加上就不一定为最大值) mx=a[n];//初始mx for(int i=n-1;i>=1;i--) { g[i]=max(a[i+1]+g[i+1],a[i+1]); G[i]=max(g[i],mx); mx=G[i];//同上，滚动mx } for(int i=1;i<n;i++)//枚举断点 ans=max(ans,F[i]+G[i]); printf("%d\n",ans); ans=-1e8; } }
