Hdu 2923 MAX Average Problem(DP_スロープ最適化)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2993
長さnのシーケンスが与えられ、その中から連続した長さがmより大きいサブシーケンスがサブシーケンスの平均値を最小にする.
解題の構想:経典の傾きはDPを最適化して、04年の周維の論文《数形の結合思想を浅く話して情報学の競争の中で応用します》はとても詳しい分析があって、ここでただ実現だけを話します.
     本題では,サブシーケンス長をx,サブシーケンス内とyとし,単調キューを用いてバンプの凸性を維持する.新しい点をたどるたびに、まずキューの最後の凸点を取り除く、判断条件はy 1*x 2<=y 2*x 1((x 1,y 1)がキューの最後の点、(x 2,y 2)がキューの最後の前の点)である.  そして答えを更新するたびに,最適解であるはずのない点を削除し,判断条件はy 1*x 2<=y 2*x 1((x 1,y 1)がキューヘッダの点,(x 2,y 2)がキューヘッダの次の点)である.
     私の第1回acコード700+ms、第2回入力外挂をプラスして312 msになって、それからsum配列をdoubleからintに変えて281 ms、Rank 3.   
テストデータ:
Input: 10 6 6 4 2 10 3 8 5 9 4 1 1 1 1 10 3 1 2 3 1 2 3 4 5 6 1 Output: 6.50 1.00 5.00
C艹コード:

#include <stdio.h>
#include <string.h>
#define MAX 100001


double ans;
int sum[MAX],n,len;
int qu[MAX],head,tail;


double Solve_DP() {

    int i,j,k,pre,cur;
    double x1,x2,y1,y2;


    ans = 0;
    qu[tail] = 0;
    head = tail = 0;


    for (i = len; i <= n; ++i) {

        cur = i - len;
        while (head < tail) {
            //          
            pre = qu[tail];
            x1 = cur - pre;
            y1 = sum[cur] - sum[pre];
            pre = qu[tail-1];
            x2 = cur - pre;
            y2 = sum[cur] - sum[pre];


            if (y1 * x2 <= y2 * x1) tail--;
            else break;
        }


        qu[++tail] = cur;
        while (head < tail) {
            //        
            cur = i;
            pre = qu[head];
            x1 = cur - pre;
            y1 = sum[cur] - sum[pre];
            pre = qu[head+1];
            x2 = cur - pre;
            y2 = sum[cur] - sum[pre];


            if (y1 * x2 <= y2 * x1) head++;
            else break;
        }


        pre = qu[head];
        double temp = (sum[i] - sum[pre]) * 1.0 / (i - pre);
        if (temp > ans) ans = temp;
    }


    return ans;
}
int Input() {
    
    char ch = ' ';
    while (ch < '0' || ch > '9')
        ch = getchar();
    int x = 0;
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0',ch = getchar();
    return x;
}


int main()
{
    int i,j,k;


    while (scanf("%d%d",&n,&len) != EOF) {

        for (i = 1; i <= n; ++i)
            k = Input(),sum[i] = sum[i-1] + k;


        ans = Solve_DP();
        printf("%.2lf
",ans);
    }
}

ZeroClockオリジナルですが、私たちは兄弟なので転載できます.