[POJ 1093] | Eurce's Blog

题意：输入行长度值n，以及一篇文章，要将文章重新排版，使得”坏值”和最小。若某行只含一个单词，则坏值为500。包含多个单词的行，单词间每个长度为k的间隔，其坏值为(k-1)^2。

这题之前做CLRS时见过类似的（第二版习题15-2），当时也是想了很久才推出公式：用dp[i][j]保存到第i行结束时，打印了前j个单词的最小坏值。那么dp[i][j]=min{dp[i-1][k-1]+bd[n-sum{w[l]|k<=l<=j}][j-k]}，其中w[l]为第l个单词的长度，bd[p][q]为预处理计算出来的一行有p个空格和q个间隔时的坏值。状态转移时注意下标边界，并需要记录父状态。这里对于相同坏值的方案，要输出使各间隔长度值字典序最小的，那么每次dp使，总是使更多单词尽量在之前打印即可。输出时，首先找到最小坏值对应的行数，根据父状态一层层回退，记录每行要打印多少个单词；然后逐个单词处理输出即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define WN 1000

int n,sl,w[10000],wl,bd[81][81];
char s[10000];
int dp[WN][WN],p[WN][WN],dpi,dpj[WN],dpw[WN];

void init()
{
    int i,j,k,l;
    char c;
    sl=wl=0;
    memset(w,0,sizeof w);
    memset(s,0,sizeof s);
    memset(dp,-1,sizeof dp);
    getchar();
    while((c=getchar())!='\n')
    {
        while(c!='\n')
        {
            while(c==' ')
                c=getchar();
            if(c=='\n')
                break;
            while(c!=' '&&c!='\n')
            {
                w[wl]++;
                s[sl++]=c;
                c=getchar();
            }
            wl++;
        }
    }
}

void pnt(int wi,int si)
{
    int i;
    for(i=0;i<w[wi];i++)
        printf("%c",s[si+i]);
}

void pntw(int i)
{
    while(i--)
        printf(" ");
}

void solve()
{
    int i,j,k,l,pj,km;
    for(i=0,j=w[i];i<wl&&i+j<=n;i++,j+=w[i])
        dp[0][i]=bd[n-j][i];
    for(i=1;i<wl;i++)
    {
        for(j=i;j<wl&&dp[i-1][j-1]!=-1;j++)
        {
            for(k=j,l=w[k];k<wl&&l+k-j<=n;k++,l+=w[k])
            {
                if(dp[i][k]==-1)
                {
                    p[i][k]=j;
                    dp[i][k]=dp[i-1][j-1]+bd[n-l][k-j];
                }
                else if(dp[i-1][j-1]+bd[n-l][k-j]
                        <=dp[i][k])
                {
                    p[i][k]=j;
                    dp[i][k]=dp[i-1][j-1]+bd[n-l][k-j];
                }
            }
        }
    }
    for(i=0,j=0x7fffffff;i<wl;i++)
        if(dp[i][wl-1]!=-1)
        {
            if(dp[i][wl-1]<j)
            {
                j=dp[i][wl-1];
                dpi=i+1;
            }
        }
    dpj[dpi-1]=wl;
    for(i=dpi-1;i;i--)
        dpj[i-1]=p[i][dpj[i]-1];
    for(i=j=0;i<dpi;i++)
        for(dpw[i]=n;j<dpj[i];j++)
            dpw[i]-=w[j];
    for(i=j=pj=l=0;i<dpi;i++)
    {
        if(dpj[i]>j+1)
        {
            k=dpw[i]/(dpj[i]-j-1);
            km=(dpj[i]-j-1)-dpw[i]%(dpj[i]-j-1);
            for(;j<dpj[i]-1;j++)
            {
                pnt(j,l);
                l+=w[j];
                if(km)
                {
                    km--;
                    pntw(k);
                }
                else
                    pntw(k+1);
            }
        }
        pnt(j,l);
        l+=w[j];
        j++;
        puts("");
        pj=j;
    }
    puts("");
}

int main()
{
    int i,j,k,l;
    for(i=0;i<81;i++)
    {
        bd[i][0]=500;
        for(j=1;j<=i;j++)
        {
            k=i/j;
            if(i%j==0)
                bd[i][j]=j*(k-1)*(k-1);
            else
            {
                l=i%j;
                bd[i][j]=(j-l)*(k-1)*(k-1)+l*k*k;
            }
        }
    }
    while(~scanf("%d",&n)&&n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define WN 1000

int n,sl,w[10000],wl,bd[81][81];

char s[10000];

int dp[WN][WN],p[WN][WN],dpi,dpj[WN],dpw[WN];

void init()

{

int i,j,k,l;

char c;

sl=wl=0;

memset(w,0,sizeof w);

memset(s,0,sizeof s);

memset(dp,-1,sizeof dp);

getchar();

while((c=getchar())!='\n')

{

while(c!='\n')

{

while(c==' ')

c=getchar();

if(c=='\n')

break;

while(c!=' '&&c!='\n')

{

w[wl]++;

s[sl++]=c;

c=getchar();

}

wl++;

}

void pnt(int wi,int si)

{

int i;

for(i=0;i<w[wi];i++)

printf("%c",s[si+i]);

}

void pntw(int i)

{

while(i--)

printf(" ");

}

void solve()

{

int i,j,k,l,pj,km;

for(i=0,j=w[i];i<wl&&i+j<=n;i++,j+=w[i])

dp[0][i]=bd[n-j][i];

for(i=1;i<wl;i++)

{

for(j=i;j<wl&&dp[i-1][j-1]!=-1;j++)

{

for(k=j,l=w[k];k<wl&&l+k-j<=n;k++,l+=w[k])

{

if(dp[i][k]==-1)

{

p[i][k]=j;

dp[i][k]=dp[i-1][j-1]+bd[n-l][k-j];

}

else if(dp[i-1][j-1]+bd[n-l][k-j]

<=dp[i][k])

{

p[i][k]=j;

dp[i][k]=dp[i-1][j-1]+bd[n-l][k-j];

}

for(i=0,j=0x7fffffff;i<wl;i++)

if(dp[i][wl-1]!=-1)

{

if(dp[i][wl-1]<j)

{

j=dp[i][wl-1];

dpi=i+1;

}

dpj[dpi-1]=wl;

for(i=dpi-1;i;i--)

dpj[i-1]=p[i][dpj[i]-1];

for(i=j=0;i<dpi;i++)

for(dpw[i]=n;j<dpj[i];j++)

dpw[i]-=w[j];

for(i=j=pj=l=0;i<dpi;i++)

{

if(dpj[i]>j+1)

{

k=dpw[i]/(dpj[i]-j-1);

km=(dpj[i]-j-1)-dpw[i]%(dpj[i]-j-1);

for(;j<dpj[i]-1;j++)

{

pnt(j,l);

l+=w[j];

if(km)

{

km--;

pntw(k);

}

else

pntw(k+1);

}

pnt(j,l);

l+=w[j];

j++;

puts("");

pj=j;

}

puts("");

}

int main()

{

int i,j,k,l;

for(i=0;i<81;i++)

{

bd[i][0]=500;

for(j=1;j<=i;j++)

{

k=i/j;

if(i%j==0)

bd[i][j]=j*(k-1)*(k-1);

else

{

l=i%j;

bd[i][j]=(j-l)*(k-1)*(k-1)+l*k*k;

}

while(~scanf("%d",&n)&&n)

{

init();

solve();

}

return 0;

}

ps: 这题考察的算法貌似很有实用价值呢……不过现在的文本处理程序，恐怕是要比这复杂十倍以上的吧……