poj - 1093 - Formatting Text（dp）

poj - 1093 - Formatting Text（dp）

題意：輸入一段短文（所有字符總數不超過10000），要求格式化成兩端對齊（每行長度為n，1 <= n <= 80）的方式輸出並使得總壞值最小（一個空隙的壞值是這個空隙的空格總數減1後的平方），若有多種方案輸出空格數字典序最小方案。

——>>狀態：dp[i]表示從第i個單詞開始到最後一個單詞的最小總壞值（第i個單詞是這一行的第1個單詞）

狀態轉移方程：dp[i] = min(dp[i], dp[j + 1] + Badness(i, j));（Badness(i, j)表示第i個單詞到第j個單詞放在一行的最小總壞值，貪心一下，空格平均的時候最小。。）

如果一行只有一個單詞，那麼輸出這個單詞後，後面要不要補空格呢？答案：poj 1093補與不補都可以AC，而在zoj 1147不能補。。

想想，這個程序可以給自已用來做文本對齊呢。。好題。。實用。。

#include 
#include 

const int MAXL = 80 + 10;
const int MAXN = 10000 + 10;

char szLine[MAXN];
char szWord[MAXN][MAXL];
int n;
int nWordCnt;
int dp[MAXN];
int nLastTo[MAXN];
int nSum[MAXN];

void Read()
{
    getchar();
    nWordCnt = 0;
    while (gets(szLine))
    {
        if (szLine[0] == '') break;
        sscanf(szLine, %s, szWord[++nWordCnt]);
        for (int i = 0; szLine[i] != ''; ++i)
        {
            if (szLine[i] == ' ')
            {
                while (szLine[i] == ' ')
                {
                    i++;
                }
                sscanf(szLine + i, %s, szWord[++nWordCnt]);
            }
        }
    }
}

void Init()
{
    nSum[0] = 0;
    for (int i = 1; i <= nWordCnt; ++i)
    {
        nSum[i] = nSum[i - 1] + strlen(szWord[i]);
    }
}

int Sum(int i, int j)
{
    return nSum[j] - nSum[i - 1];
}

int LeastLen(int i, int j)
{
    return Sum(i, j) + j - i;
}

int Badness(int i, int j)
{
    if (i == j)
    {
        return 500;
    }
    int nBlankCnt = n - Sum(i, j);
    int nGapCnt = j - i;
    int nGapLen = nBlankCnt / nGapCnt;
    int nRemain = nBlankCnt % nGapCnt;
    return (nGapLen - 1) * (nGapLen - 1) * (nGapCnt - nRemain) + nGapLen * nGapLen * nRemain;
}

void Dp()
{
    memset(dp, 0x3f, sizeof(dp));
    dp[nWordCnt + 1] = 0;
    for (int i = nWordCnt; i >= 1; --i)
    {
        for (int j = i; j <= nWordCnt && LeastLen(i, j) <= n; ++j)
        {
            if (dp[j + 1] + Badness(i, j) <= dp[i])
            {
                dp[i] = dp[j + 1] + Badness(i, j);
                nLastTo[i] = j;
            }
        }
    }
}

void PrintBlank(int nNum)
{
    for (int i = 0; i < nNum; ++i)
    {
        putchar(' ');
    }
}

void Output()
{
    int nL = 1;
    while (true)
    {
        int nR = nLastTo[nL];
        if (nL == nR)
        {
            puts(szWord[nL]);
        }
        else
        {
            int nBlankCnt = n - Sum(nL, nR);
            int nGapCnt = nR - nL;
            int nGapLen = nBlankCnt / nGapCnt;
            int nRemain = nBlankCnt % nGapCnt;
            printf(%s, szWord[nL]);
            for (int i = 0; i < nGapCnt - nRemain; ++i)
            {
                PrintBlank(nGapLen);
                printf(%s, szWord[nL + 1 + i]);
            }
            for (int i = 0; i < nRemain; ++i)
            {
                PrintBlank(nGapLen + 1);
                printf(%s, szWord[nR - nRemain + 1 + i]);
            }
            puts();
        }
        if (nR == nWordCnt) break;
        nL = nR + 1;
    }
    puts();
}

int main()
{
    while (scanf(%d, &n) == 1 && n)
    {
        Read();
        Init();
        Dp();
        Output();
    }

    return 0;
}