NOI 2009 詩人小G

問題簡述

有N個詩句需要被排版爲若干行,順序不能改變。一行內可以有若干個詩句,相鄰詩句之間有一個空格。定義行標準長度L,每行的不協調度爲|實際長度-L|P,整首詩的不協調度就是每行不協調度之和。任務是安排一種排版方案,使得整首詩的不協調度最小。

問題建模

這是一個最優化問題,抽象成動態規劃模型。設第i個詩句的長度爲Len[i],前i個詩句的總長度爲SumL[i],clip_image002[4]。F[i]爲對前i個詩句排版的最小不協調度。

解法1 樸素的動態規劃

算法描述
顯然每個F[i]可以被分解爲F[j]和第j+1…i個句子組成一行的狀態,所以狀態轉移方程爲

clip_image004[4]

簡化後,可以書寫成

clip_image006

在具體實現時,應記錄每個狀態的決策,以便於輸出合法方案。考慮到“最小的不協調度超過1018輸出"Too hard to arrange"”,爲防止64位整型運算溢出,可以先用浮點數類型計算,然後再用整型算出具體值。

複雜度分析
狀態數爲O(N),每次轉移需要以O(N)的時間枚舉j,所以時間複雜度爲O(N2)。在實際測試中通過了測試點1,2,3,得到30分。

參考程序

/* 
 * Problem: NOI2009 poet
 * Author: Guo Jiabao
 * Time: 2009.9.22 13:30
 * State: Solved
 * Memo: 樸素動態規劃
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long big;

const int MAXN=100001,SMAXL=32;
const big INF=~0ULL>>1,LIMIT=1000000000000000000LL;

big F[MAXN],sumL[MAXN];
int N,L,P;
int Len[MAXN],deci[MAXN],sel[MAXN];
char sent[MAXN][SMAXL];

void init()
{
    scanf("%d%d%d\n",&N,&L,&P);
    for (int i=1;i<=N;++i)
    {
        gets(sent[i]);
        Len[i] = strlen(sent[i]);
        sumL[i] = sumL[i-1] + Len[i];
    }
}

big power(big a)
{
    big t=1;
    double dt=1;
    if (a < 0)
        a = -a;
    for (int i=1;i<=P;i++)
    {
        dt *= a;
        if (dt > LIMIT)
            return INF;
        t *= a;
    }
    return t;
}

void solve()
{
    int i,j,k;
    big minv,t;
    for (i=1;i<=N;++i)
    {
        minv = INF;
        for (j=0;j<=i-1;++j)
        {
            t = power(sumL[i] - sumL[j] + i-j-1 - L);
            if ( double(t) + double(F[j]) <= LIMIT && t + F[j] < minv)
            {
                minv = t + F[j];
                k = j;
            }
        }
        F[i] = minv;
        deci[i] = k;
    }
}

void print()
{
    if (F[N] <= LIMIT)
    {
        cout << F[N] << endl;
        int i,j;
        for (i=N,j=0;i;i=deci[i])
            sel[++j] = i;
        for (i=0;j;j--)
        {
            for (++i;i < sel[j];++i)
                printf("%s ",sent[i]);
            printf("%s\n",sent[i]);
        }
    }
    else
        printf("Too hard to arrange\n");
    printf("--------------------\n");
}

int main()
{
    int i,T;
    freopen("poet.in","r",stdin);
    freopen("poet.out","w",stdout);
    scanf("%d",&T);
    for (i=1;i<=T;i++)
    {
        init();
        solve();
        print();
    }
    return 0;
}

解法2 貪心的動態規劃

算法描述
觀察測試點4,5的N值較大,而L值較小,因此可以限制每行長度,以優化狀態轉移。

clip_image008

實現時應讓j從i-1到0枚舉,當j<i-1時一旦發現行長度超過2L,即停止枚舉j,因爲j繼續減少會讓行長度繼續增加。

算法證明
一個空行的不協調度爲LP,若一行內包含多餘一個句子,且行長度L’>2L,則行不協調度(L’-L)P>LP。把該行拆分爲兩行後,設長度分別爲L1和L2,L1+L2=L’-1,拆分後的兩行不協調度之和爲(L1-L)P+(L2-L)P<(L’-L)P,所以拆分爲兩行後比合在一行好。因此應保證當一行包含多於一個句子時,行長度<=2L。

複雜度分析
狀態數爲O(N),每次轉移需要O(Min{N,L})的時間,所以時間複雜度爲O(Min{N2,NL})。在實際測試中通過了前5個測試點,得到50分。

參考程序

/* 
 * Problem: NOI2009 poet
 * Author: Guo Jiabao
 * Time: 2009.9.22 13:51
 * State: Solved
 * Memo: 樸素動態規劃 剪枝
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long big;

const int MAXN=100001,SMAXL=32;
const big INF=~0ULL>>1,LIMIT=1000000000000000000LL;

big F[MAXN],sumL[MAXN];
int N,L,P;
int Len[MAXN],deci[MAXN],sel[MAXN];
char sent[MAXN][SMAXL];

void init()
{
    scanf("%d%d%d\n",&N,&L,&P);
    for (int i=1;i<=N;++i)
    {
        gets(sent[i]);
        Len[i] = strlen(sent[i]);
        sumL[i] = sumL[i-1] + Len[i];
    }
}

big power(big a)
{
    big t=1;
    double dt=1;
    if (a < 0)
        a = -a;
    for (int i=1;i<=P;i++)
    {
        dt *= a;
        if (dt > LIMIT)
            return INF;
        t *= a;
    }
    return t;
}

void solve()
{
    int i,j,k;
    big minv,t;
    for (i=1;i<=N;++i)
    {
        minv = INF;
        for (j=i-1;j>=0;--j)
        {
            t = sumL[i] - sumL[j] + i-j-1 - L;
            if (j < i-1 && t > L + L)
                break;
            t = power(t);
            if ( double(t) + double(F[j]) <= LIMIT && t + F[j] < minv)
            {
                minv = t + F[j];
                k = j;
            }
        }
        F[i] = minv;
        deci[i] = k;
    }
}

void print()
{
    if (F[N] <= LIMIT)
    {
        cout << F[N] << endl;
        int i,j;
        for (i=N,j=0;i;i=deci[i])
            sel[++j] = i;
        for (i=0;j;j--)
        {
            for (++i;i < sel[j];++i)
                printf("%s ",sent[i]);
            printf("%s\n",sent[i]);
        }
    }
    else
        printf("Too hard to arrange\n");
    printf("--------------------\n");
}

int main()
{
    int i,T;
    freopen("poet.in","r",stdin);
    freopen("poet.out","w",stdout);
    scanf("%d",&T);
    for (i=1;i<=T;i++)
    {
        init();
        solve();
        print();
    }
    return 0;
}

解法3 凸殼優化動態規劃

算法描述
觀察發現測試點6,7的N和L都很大,而P值爲2。經分析發現可以使用單調隊列維護凸殼。

算法分析與證明
當P=2時,觀察狀態轉移方程

clip_image010

設對於F[i]的最優決策爲k,那麼對於所有的j≠k,均滿足

clip_image012

clip_image014clip_image016,則有

clip_image018

clip_image020

clip_image022

因爲SumL爲單調增函數,所以A,B均爲增函數。當B[j]>B[k] ⇒j>k,有

clip_image024

相對的,當j<k時有

clip_image026

如果把(B[i],F[i]+B[i]2)看作是二維平面上的一個點,那麼clip_image028恰爲斜率公式。因此對於最優決策k,應保證在對應點右邊任意一個決策j的對應點,滿足直線kj斜率大於2A[i];在對應點左邊任意一個決策j的對應點,滿足直線kj斜率小於2A[i]。

image

因此所有最優決策在平面上的對應點連線就是一個斜率遞增的凸殼。

image

具體實現時,用單調隊列維護每個點(B[i],F[i]+B[i]2),每在隊尾加入一個新的點,判斷斜率是否遞增,如果不是則不斷刪除隊尾元素。求F[i]的最優決策只需不斷在隊首刪除點,直到隊首兩點組成的直線斜率剛好大於2A[i],最優決策就是左端點的對應決策。

複雜度分析
用單調隊列每次維護凸殼的時間複雜度爲均攤O(1),所以時間複雜度爲O(N)。經測試可以通過測試點6,7,配合解法2,一共可以得到70分。

參考程序

/* 
 * Problem: NOI2009 poet
 * Author: Guo Jiabao
 * Time: 2009.9.22 14:30
 * State: Solved
 * Memo: 樸素動態規劃 剪枝 凸殼優化
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long big;

const int MAXN=100001,SMAXL=32;
const big INF=~0ULL>>1,LIMIT=1000000000000000000LL;

struct MonoQueue
{
    struct point
    {
        big x,y;
        int id;
    }P[MAXN];

    int head,tail;

    void initialize()
    {
        head = 0;
        tail = -1;
    }

    void insert(big x,big y,int id)
    {
        point p={x,y,id};
        for (;head + 1 <= tail;--tail)
        {
            double k1,k2;
            k1 = (p.y - P[tail].y) / double(p.x - P[tail].x);
            k2 = (P[tail].y - P[tail-1].y) / double(P[tail].x - P[tail-1].x);
            if (k1 > k2)
                break;
        }
        P[++tail] = p;
    }

    int getmin(big v)
    {
        for (;head + 1 <= tail;++head)
        {
            double k = (P[head+1].y - P[head].y) / double(P[head+1].x - P[head].x);
            if (k > v)
                break;
        }
        return P[head].id;
    }
}MQ;

big F[MAXN],sumL[MAXN],A[MAXN],B[MAXN];
int N,L,P;
int Len[MAXN],deci[MAXN],sel[MAXN];
char sent[MAXN][SMAXL];

void init()
{
    scanf("%d%d%d\n",&N,&L,&P);
    for (int i=1;i<=N;++i)
    {
        gets(sent[i]);
        Len[i] = strlen(sent[i]);
        sumL[i] = sumL[i-1] + Len[i];
    }
}

big power(big a)
{
    big t=1;
    double dt=1;
    if (a < 0)
        a = -a;
    for (int i=1;i<=P;i++)
    {
        dt *= a;
        if (dt > LIMIT)
            return INF;
        t *= a;
    }
    return t;
}

void tq()
{
    int i,j;
    big t;
    MQ.initialize();
    MQ.insert(0,0,0);
    for (i=1;i<=N;i++)
    {
        B[i] = sumL[i] + i;
        A[i] = B[i] - 1 - L;
    }
    for (i=1;i<=N;i++)
    {
        j = MQ.getmin(A[i] + A[i]);
        t = power(sumL[i] - sumL[j] + i-j-1 - L);
        if ( double(t) + double(F[j]) <= LIMIT )
            F[i] = F[j] + t;
        else
            F[i] = INF;
        if ( double(B[i]) * double(B[i]) + F[i] <= LIMIT)
            t = F[i] + B[i] * B[i];
        else
            t = INF;
        MQ.insert(B[i],t,i);
        deci[i] = j;
    }
}

void simple()
{
    int i,j,k;
    big minv,t;
    k = -1;
    for (i=1;i<=N;++i)
    {
        minv = INF;
        for (j=i-1;j>=0;--j)
        {
            t = sumL[i] - sumL[j] + i-j-1 - L;
            if (t > L + L)
                break;
            t = power(t);
            if ( double(t) + double(F[j]) <= LIMIT && t + F[j] < minv)
            {
                minv = F[j] + t;
                k = j;
            }
        }
        F[i] = minv;
        deci[i] = k;
    }
}

void solve()
{
    if (P == 2)
        tq();
    else
        simple();
}

void print()
{
    if (F[N] <= LIMIT)
    {
        cout << F[N] << endl;
        int i,j;
        for (i=N,j=0;i;i=deci[i])
            sel[++j] = i;
        for (i=0;j;j--)
        {
            for (++i;i < sel[j];++i)
                printf("%s ",sent[i]);
            printf("%s\n",sent[i]);
        }
    }
    else
        printf("Too hard to arrange\n");
    printf("--------------------\n");
}

int main()
{
    int i,T;
    freopen("poet.in","r",stdin);
    freopen("poet.out","w",stdout);
    scanf("%d",&T);
    for (i=1;i<=T;i++)
    {
        init();
        solve();
        print();
    }
    return 0;
}

解法4 決策單調性優化動態規劃

算法描述
可以觀察到或證明出,該狀態轉移方程滿足決策單調性。因此我們可以使用雙端隊列維護每個決策區間,對於每個新決策使用二分查找確定位置並更新決策隊列。

算法證明
再次觀察狀態轉移方程

clip_image034

clip_image036,狀態轉移方程可以化爲1D/1D標準形式

clip_image038

要證明上述狀態轉移方程具有決策單調性,k(i)表示F[i]的最優決策,即

clip_image040

當且僅當滿足四邊形不等式

clip_image042

clip_image044clip_image046clip_image048。其中clip_image050

於是clip_image052。要證明①,只需證明

clip_image054

clip_image056clip_image058,則②等價於

clip_image060

clip_image062

因爲clip_image064,且D[i+1]恆爲正數,所以S<T。於是要證明③,只需證明下列函數在整數域內(非嚴格)單調遞增

clip_image066

(1)若P爲偶數
clip_image068,求導得clip_image070

因爲clip_image072,P-1爲奇數,所以clip_image074clip_image076恆成立,f(x)在實數域內單調遞增。

(2)若P爲奇數

(a)當X-C>=0
clip_image068[1],求導得clip_image070[1]

因爲clip_image080,P-1爲偶數,所以clip_image074[1]clip_image076[1]恆成立,f(x)在實數域內單調遞增。

(b)當X<=0
clip_image084,求導得clip_image086。因爲P-1爲偶數,clip_image076[2]恆成立,f(x)在實數域內單調遞增。

(c)當0<X<C
clip_image090,求導得clip_image086[1]。因爲P-1爲偶數,clip_image076[3]恆成立,f(x)在實數域內單調遞增。

綜上所述,f(x)在實數域內單調遞增,即在正數域內單調遞增,因而③②①依次得證。

因此狀態轉移方程clip_image006[1]具有決策單調性。

複雜度分析
狀態數爲O(N),每次維護決策隊列的時間爲O(logN),所以時間複雜度爲O(NlogN)。在測試中通過了全部測試點,拿到了100分。

參考程序

/* 
 * Problem: NOI2009 poet
 * Author: Guo Jiabao
 * Time: 2009.9.22 16:30
 * State: Solved
 * Memo: 動態規劃 決策單調性
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long big;

const int MAXN=100001,SMAXL=32;
const big LIMIT=1000000000000000000LL;

struct interval
{
    int s,t,deci;
}di[MAXN];

double F[MAXN];
int N,L,P,Stop;
int Len[MAXN],deci[MAXN],sel[MAXN];
char sent[MAXN][SMAXL];
big G[MAXN],sumL[MAXN];

void init()
{
    scanf("%d%d%d\n",&N,&L,&P);
    for (int i=1;i<=N;++i)
    {
        gets(sent[i]);
        Len[i] = strlen(sent[i]);
        sumL[i] = sumL[i-1] + Len[i];
    }
}

double dpower(double a)
{
    double t=1;
    if (a < 0)
        a = -a;
    for (int i=1;i<=P;i++)
        t *= a;
    return t;
}

double getF(int i,int j)
{
    double t = dpower(sumL[i] - sumL[j] + i-j-1 - L);
    return F[j] + t;
}

big power(big a)
{
    big t=1;
    double dt=1;
    if (a < 0)
        a = -a;
    for (int i=1;i<=P;i++)
    {
        dt *= a;
        if (dt > LIMIT)
            return LIMIT+1;
        t *= a;
    }
    return t;
}

big getG(int i,int j)
{
    big t = power(sumL[i] - sumL[j] + i-j-1 - L);
    if (F[j] + t <= LIMIT)
        return G[j] + t;
    else
        return LIMIT + 1;
}

void update(int i)
{
    while (di[Stop].s > i && getF(di[Stop].s,i) < getF(di[Stop].s,di[Stop].deci) )
    {
        di[Stop-1].t = di[Stop].t;
        Stop --;
    }
    int a=di[Stop].s,b=di[Stop].t,m;
    if (a < i+1)
        a = i+1;
    while (a+1<b)
    {
        m = (a + b) >> 1;
        if ( getF(m,di[Stop].deci) < getF(m,i) )
            a = m;
        else
            b = m-1;
    }
    if ( a < b && getF(b,di[Stop].deci) < getF(b,i) )
        a = b;
    if (a+1 <= di[Stop].t)
    {
        di[Stop + 1].s = a+1;
        di[Stop + 1].t = di[Stop].t;
        di[Stop + 1].deci = i;
        di[Stop].t = a;
        ++Stop;
    }
}

void solve()
{
    int i,j;
    di[Stop=1].s = 1;
    di[Stop].t = N;
    for (i=j=1;i<=N;i++)
    {
        if (i > di[j].t)
            ++j;
        deci[i] = di[j].deci;
        F[i] = getF(i,deci[i]);
        update(i);
    }
    for (i=1;i<=N;i++)
        G[i] = getG(i,deci[i]);
}

void print()
{
    if (G[N] <= LIMIT)
    {
        cout << G[N] << endl;
        int i,j;
        for (i=N,j=0;i;i=deci[i])
            sel[++j] = i;
        for (i=0;j;j--)
        {
            for (++i;i < sel[j];++i)
                printf("%s ",sent[i]);
            printf("%s\n",sent[i]);
        }
    }
    else
        printf("Too hard to arrange\n");
    printf("--------------------\n");
}

int main()
{
    int i,T;
    freopen("poet.in","r",stdin);
    freopen("poet.out","w",stdout);
    scanf("%d",&T);
    for (i=1;i<=T;i++)
    {
        init();
        solve();
        print();
    }
    return 0;
}

相關日誌