澳门新葡亰平台官网HDU1244 Max Sum Plus Plus Plus

by admin on 2020年1月28日

#include< stdio.h >
#include< string.h >
int am[ 21 ]={0}, ansum[ 1001 ]={0}, lenam[ 21 ]={0}, an[ 1001
]={0}, sum[ 21 ][ 1001 ]={0};
int main( )
{
 int max, i, j, max_res, n, m;
 while( scanf( “%d”, &n ) != EOF && n )
 {
  scanf( “%d”, &m );
  for( i = 0; i <= m; i ++ )
   memset( sum[ i ], 0, sizeof( sum[ i ] ) );
  lenam[ 1 ] = 0;
  lenam[ 0 ] = 0;
  for( i = 1; i <= m; i ++ )
  {
   scanf( “%d”, &am[ i ] );
   lenam[ i ] += am[ i ];
  }
  ansum[ 1 ] = 0;
  ansum[ 0 ] = 0;
  for( i = 1; i <= n; i ++ )
  {
   scanf( “%d”, &an[ i ] );
   ansum[ i ] = ansum[i-1] + an[ i ];
  }
  for( i = 1; i <= m; i ++ )
  {
   max = ansum[ lenam[ i-1 ] ];
   for( j = lenam[ i-1 ] + am[ i ]; j <= n; j ++ )
   {
    if( max < sum[ i-1 ][ j – am[ i ] ] )
     max = sum[ i-1 ][ j – am[ i ] ];
    sum[ i ][ j ] = max + ansum[ j ] – ansum[ j-am[ i ] ];
   }
  }
  max_res = ansum[ lenam[ m ] ];
  for( i = 1 + lenam[ m ]; i <= n; i ++ )
   if( sum[ m ][ i ] > max_res )
    max_res = sum[ m ][ i ];
  printf( “%dn”, max_res );
  for( i = 0; i <= 20; i ++ )
   memset( sum[ i ], 0, sizeof( sum[ i ] ) );
  for( i = 0; i <= 20; i ++)
   lenam[ i ] = 0;
 }
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图