做网站需要哪些人才,丰台网站关键词优化,楚雄做网站,建行网站数组 a 中有 M 个数 #xff0c; 将 M 个数分成 N 组 #xff0c; 并且每组中的数据顺序和原数组中的顺序保持一致#xff0c;求 N 组中的数据之和最大为多少#xff1f; 向 dp 数组中赋初始值 #xff0c;如果 M N #xff0c;则 dp[ i ][ i ] dp[ i - 1 ][ i - 1 ] … 数组 a 中有 M 个数 将 M 个数分成 N 组 并且每组中的数据顺序和原数组中的顺序保持一致求 N 组中的数据之和最大为多少 向 dp 数组中赋初始值 如果 M N 则 dp[ i ][ i ] dp[ i - 1 ][ i - 1 ] a[ i ] ; 若N为1时 即为求连续子串最大和问题 假设dp[ 1 ][ i ] ( 2 i M) 代表 与第 i 个数组成连续子串的最大和当dp[ 1 ][ i - 1 ] 0 时 a[ i ] 独立作为一个子串 即 dp[ 1 ][ i ] max ( dp[ 1 ][ i -1 ] a[ i ] , a[ i ] ) ;很需要注意的一点是dp[ 1 ][ i ] 不一定是 i 个数中连续子串的最大和。 分别求出数组中有一个数、两个数、三个数……M个数中连续子串的最大和用dp[ i ][ 1 ] 来表示 若N为2时表示将M个数分成 2 组 求两组数中的和最大 dp[ 2 ][ i ] ( 3 i M ) 代表 与第 i 个数组成连续子串形成两个连续子串中第2个子串的最大和 可知第二个子串可以单独成为一段最终形成两段也可以和上一个段一起形成一段最终形成两段 所以 dp[M][N] 代表 与第M个数组成的连续子串的最大和但不一定是 M 个数中连续子串的最大和 与第 M 个数组成连续子串时 第 M 个数可以与第 M-1 个数组成的子串组合也可以独立作为一个子串 与 M-1 个数组成的N-1组连续子串中最大和组合 才能达到分成 N 组的效果 最后输出dp数组中最大值即为 N 组中数据之和的最大值 下面给出相应的代码 #includeiostream
using namespace std ;
#define M 100005
#define max(x,y) ((x) (y) ? (x) : (y))
int a[ M ] , dp[ M ][ M ] ;
int main() {int k , n ;while(cin k n) {int i ;for(i 1 ; i n ; i)cin a[i] ;memset(dp,0,sizeof(dp)) ;for(i 1 ; i k ; i) {dp[i][i] dp[i-1][i-1] a[i] ;dp[i-1][i] max(dp[i-1][i],dp[i-1][i-1]) ;for(int j i 1 ; j n ; j) {dp[i][j] max(dp[i-1][j-1]a[j],dp[i][j-1]a[j]) ;dp[i-1][j] max(dp[i-1][j],dp[i-1][j-1]) ;}}int max1 -(130) ;for(i k ; i n ; i)max1 max(max1,dp[k][i]) ;cout max1 endl ;}return 0 ;
}上面的代码空间复杂度比较高但通过观察可以得到依照滚动数组的思想让dp数组的行数为2在两行中循环这样轻易一改省去了很多空间 有木有很强大 思维决定到效率 #includeiostream
using namespace std ;
#define M 100005
#define max(x,y) ((x) (y) ? (x) : (y))
int a[ M ] , dp[ 2 ][ M ] ;
int main() {int k , n ;while(cin k n) {int i ;for(i 1 ; i n ; i)cin a[i] ;memset(dp,0,sizeof(dp)) ;int t 0 ;for(i 1 ; i k ; i) {t !t ;dp[t][i] dp[!t][i-1] a[i] ;dp[!t][i] max(dp[!t][i],dp[!t][i-1]) ;for(int j i 1 ; j n ; j) {dp[t][j] max(dp[!t][j-1]a[j],dp[t][j-1]a[j]) ;dp[!t][j] max(dp[!t][j],dp[!t][j-1]) ;}}int max1 -(130) ;for(i k ; i n ; i)max1 max(max1,dp[k1][i]) ;cout max1 endl ;}return 0 ;
}转载于:https://www.cnblogs.com/NYNU-ACM/p/4237471.html
