很久没接触ACM题偶尔看到了做一道。
原题的详见POJ-2479。
此题看起来最简单的想法肯定是枚举S1,t1,s2,t2。显然的，这种枚举方法是不可行的。那么就需要一些其他的方式。
初看我们知道了t1<s2这条信息，也就是说，如果我们把数据源拆成两份进行二分，那么我们可以将枚举的复杂度缩小到原来的一半。既然如此，那么我们计算中还会遇到什么值呢?对的，是累加和，既然使用累加函数来进行计算，那么从一个数A到另一个数B的累加和是永远不变的，这个数据可以复用。
如果只考虑累加和的计算，我们需要O(N^2)的复杂度。但是，看题目我们求的是max，所以可以使用动态规划求出最大解。
最后枚举一个t1或者S2就可以获得最终结果。
（本想写怎么思考的，然而这东西果然很难）
下面是方法：
动态转移方程：f(i) = max{f[i - 1] + a[i], a[i]}， max(i) = max{max[i-1], f[i]}
其中f(i)求的是包含a[i]在内的最大连续累加和，max(i)求的是从第一个数到第i个数，最大的累加和。
由于有两段，所以需要求f和max的逆序，也就是从N倒序开始的累加值，记为fre和maxre。
最终结果就是对枚举t1。求max[t1]+maxre[t1+1]的最大值。
1 #include<stdio.h> 2 #include<stdlib.h> 3 4 int df(){ 5 int n; 6 scanf("%d", &n); 7 int j; 8 int a[50001], f[50001], fre[50001]; 9 int max[50001], maxre[50001]; 10 for(j = 1; j <= n; j++){ 11 scanf("%d", &a[j]); 12 } 13 f[1] = a[1]; 14 fre[n] = a[n]; 15 for(j = 2; j <= n; j++){ 16 f[j] = a[j]; 17 if ((f[j-1] + a[j]) > f[j]) f[j] = f[j-1] + a[j]; 18 } 19 max[1] = f[1]; 20 // printf("%d f[j]=%d max[j]=%d ", 1, f[1], max[1]); 21 for(j = 2; j <=n; j++){ 22 if (f[j] > max[j - 1]) max[j] = f[j]; 23 else max[j] = max[j - 1]; 24 // printf("%d f[j]=%d max[j]=%d ", j, f[j], max[j]); 25 } 26 // printf(" "); 27 28 for(j = n - 1; j >= 1; j--){ 29 fre[j] = a[j]; 30 if ((fre[j+1] + a[j]) > fre[j]) fre[j] = fre[j+1] + a[j]; 31 } 32 33 maxre[n] = fre[n]; 34 // printf("%d fre[j]=%d maxre[j]=%d ", n, fre[n], maxre[n]); 35 for(j = n - 1; j >= 1; j--){ 36 if (fre[j] > maxre[j + 1]) maxre[j] = fre[j]; 37 else maxre[j] = maxre[j + 1]; 38 // printf("%d fre[j]=%d maxre[j]=%d ", j, fre[j], maxre[j]); 39 } 40 41 int t1, maxd; 42 maxd = max[1] + maxre[2]; 43 for(t1 = 2; t1 < n; t1++) 44 if ((max[t1] + maxre[t1 + 1]) > maxd) 45 maxd = max[t1] + maxre[t1 + 1]; 46 printf("%d ", maxd); 47 } 48 49 int main(){ 50 int t; 51 scanf("%d", &t); 52 int i; 53 for (i = 0; i < t; i++){ 54 df(); 55 } 56 return 0; 57 }