SRM453.5 Div2 Hard(1000) TheProduct

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;
}