Brief description:

… 问随机数列 {Ai} 的最大绝对子段合。。 (既最大子段和或最小子段和的绝对值中取较大。。) .. .
(。。Ai 取自 {-1, 1}。。。)

Analysis:

… 分析不能的我。。。只有打表找规律了。。

const int N = 100;
DB F[N], D[N], G[N], avg;
int A[N], nn, n, m;

int f(){
    int res = 0, sum = 0;

    REP(i, n){
        sum = max(0, sum + A[i]);
        checkMax(res, sum);
    }

    return res;
}

int g(){
    int res = 0, sum = 0;

    REP(i, n){
        sum = max(0, sum - A[i]);
        checkMax(res, sum);
    }

    return res;
}

void dfs(int k = 0){
    if (k == n){
        avg += max(f(), g());
    }
    else {
        FOR_1_N(A[k], -m, m){
            if (A[k])
                dfs(k+1);
        }
    }
}

int main(){

    //freopen("in.txt", "r", stdin);

    m = 1, nn = 12; FOR_N(n, 1, nn){
        avg = 0, dfs(); //avg /= pow(2.0 * m, n);
        F[n] = avg;
    }

    REP(i, nn) D[i] = F[i+1] - F[i];
    REP(i, (nn-1)/2) G[i] = D[2*(i+1)] / D[2*i];

    printf("F: ");
    REP(i, nn){
        printf("%.3lf ", F[i]);
    }
    puts("");

    printf("D: ");
    REP(i, nn-1){
        printf("%.3lf ", D[i]);
    }
    puts("");

    printf("G: ");
    REP(i, (nn-1)/2){
        printf("%.3lf ", G[i]);
    }
}

const int N = 1509;
DB F[N], D[N], G[N];
int nn, n, m;

int main(){

    //freopen("in.txt", "r", stdin);

    m = 1, nn = 1501;

    REP(i, (nn-1)/2){
        G[i] = DB (2*i+1) / (2*(i+1));
    }

    D[0] = 1;
    REP(i, nn-1){
        D[i+1] = D[i] * G[i/2];
        ++i, D[i+1] = D[i];
    }

    F[0] = 0;
    REP(i, nn-1){
        F[i+1] = F[i] + D[i];
    }

    REP_C(Case, RD()){
        printf("Case %d: %.6lf\n", Case, F[RD()]);
    }
}

Further discussion:

。。随机矩阵的最大子矩阵。。
(这个方向的推广太复杂了。。先 hold 。。。)
。。。随机序列的最大子段和。。。
(题目中可以取绝对值的限制太不自然了。。。但是去掉以后完全找不出规律。。
对数组的取值范围进行推广, {-m <= x <= m, x != 0, x 是整数}。。。 (后两个限制去掉后也变成了完全不同的问题。。) 两个弱化。。 。。只考虑前缀和 (partial sums)。。。 。。只考虑单个项目的最大值。。。

External link:

http://acm.hdu.edu.cn/showproblem.php?pid=4066
http://math.stackexchange.com/questions/139159/the-length-of-maximum-subsequence-in-a-random-sequence

Posted by xiaodao
Category: HDU
Tags: 缺少分析