HDU 1024(新最大子序列和 DP)
题意是要在一段数列中求 m 段互不重合的子数列的最大和。
动态规划，用数组 num[ ] 存储所给数列，建二维数组 dp[ ][ ] ， dp[ i ][ j ] 表示当选择了第 j 个数字( num [ j ] )时，前 j 个数字被分成 i 组的所得最大和。
那么这个最大和等于 max{ ( 前 i - 1 组的和 + 第 i 组(含num[ j - 1]) + num[ j ] )，( 前 i - 1 组的和 + num[ j ] ) }；
即 dp[ i ][ j ] = max( dp[ i ][ j - 1], dp[ i - 1 ][ k ] ) + num[ j ]；
但是这么大的二维数组开不了的，而且每次算当前状态时只需要前一状态，再之前的没什么用，（即状态具有后无效性，前面的选择不会影响后续选择）因此使用滚动数组，再干脆直接开两个一维数组，dp[ ] 和 pre[ ]，pre[ j - 1 ] 表示 j - 1 之前的数的最大和
( 不包括 num[ j - 1 ] ) ，dp[ j ] 表示选择了 num[ j ] 时前 j 个数字的最大和，
则 dp[ j ] = max( dp[ j - 1 ] ，pre[ j - 1 ] ) + num [ j ]；
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1000000; 4 int dp[maxn],pre[maxn],num[maxn]; 5 int main() 6 { 7 int n,m,tmp; 8 while(~scanf("%d%d",&m,&n)) 9 { 10 for(int i = 1; i <= n; ++i) 11 scanf("%d",&num[i]); 12 memset(dp,0,sizeof(dp)); 13 memset(pre,0,sizeof(pre)); 14 for(int i = 1; i <= m; ++i) 15 { 16 tmp = -10000000; 17 for(int k = i; k <= n; ++k) 18 { 19 dp[k] = max(dp[k-1],pre[k-1]) + num[k]; 20 pre[k-1] = tmp; 21 tmp = max(tmp,dp[k]); 22 } 23 } 24 printf("%d ",tmp); 25 } 26 return 0; 27 }