SRM453.5 Div2 Hard(1000) TheProduct
動的計画法。最後が numbers[i] である k 個の数字の積が取りうるのは、最後が numbers[i-maxDist]〜numbers[i-1] である k-1 個の数字の積に numbers[i] を乗じた値。各マスでは正負それぞれ絶対値が最小・最大であるものだけ記憶しておけばよい。
#include <vector> using namespace std; class TheProduct { public: long long maxProduct( vector<int> numbers, int k, int maxDist ); }; long long TheProduct::maxProduct( vector<int> numbers, int k, int maxDist ) { int N = (int)numbers.size(); long long t[11][50][4]; // [k][N][-max,-min,+min,+max] for ( int i=0; i<11*50; i++ ) t[0][i][0] = 0, t[0][i][1] = LLONG_MIN, t[0][i][2] = LLONG_MAX, t[0][i][3] = 0; for ( int i=0; i<N; i++ ) { if ( numbers[i] >= 0 ) t[1][i][2] = t[1][i][3] = numbers[i]; if ( numbers[i] <= 0 ) t[1][i][0] = t[1][i][1] = numbers[i]; } for ( int i=2; i<=k; i++ ) for ( int j=0; j<N; j++ ) for ( int l=max(j-maxDist,0); l<j; l++ ) { long long *c = t[i][j]; long long *p = t[i-1][l]; int n = numbers[j]; if ( n >= 0 ) { if ( p[0] != 0 ) c[0] = min( c[0], p[0]*n ); if ( p[1] != LLONG_MIN ) c[1] = max( c[1], p[1]*n ); if ( p[2] != LLONG_MAX ) c[2] = min( c[2], p[2]*n ); if ( p[3] != 0 ) c[3] = max( c[3], p[3]*n ); } if ( n <= 0 ) { if ( p[3] != 0 ) c[0] = min( c[0], p[3]*n ); if ( p[2] != LLONG_MAX ) c[1] = max( c[1], p[2]*n ); if ( p[1] != LLONG_MIN ) c[2] = min( c[2], p[1]*n ); if ( p[0] != 0 ) c[3] = max( c[3], p[0]*n ); } } long long ans = LLONG_MIN; for ( int i=0; i<N; i++ ) { if ( t[k][i][0] != 0 ) ans = max( ans, t[k][i][0] ); if ( t[k][i][1] != LLONG_MIN ) ans = max( ans, t[k][i][1] ); if ( t[k][i][2] != LLONG_MAX ) ans = max( ans, t[k][i][2] ); if ( t[k][i][3] != 0 ) ans = max( ans, t[k][i][3] ); } return ans; }