b诗人小G.doc

窗体顶端

窗体底端
您查询的关键词是：诗人小g 报告  。如果打开速度慢，可以尝试快速版；如果想保存快照，可以添加到搜藏。
(百度和网页

Beyond the Void
« NOI 2009 变换序列
NOI 2009 二叉查找树 »
一 12
NOI 2009 诗人小G
NOI Add comments1,500 views
问题简述
有N个诗句需要被排版为若干行，顺序不能改变。一行内可以有若干个诗句，相邻诗句之间有一个空格。定义行标准长度L，每行的不协调度为|实际长度-L|P，整首诗的不协调度就是每行不协调度之和。任务是安排一种排版方案，使得整首诗的不协调度最小。
问题建模
这是一个最优化问题，抽象成动态规划模型。设第i个诗句的长度为Len[i]，前i个诗句的总长度为SumL[i]，。F[i]为对前i个诗句排版的最小不协调度。
解法1 朴素的动态规划
算法描述
显然每个F[i]可以被分解为F[j]和第j+1…i个句子组成一行的状态，所以状态转移方程为

简化后，可以书写成

在具体实现时，应记录每个状态的决策，以便于输出合法方案。考虑到“最小的不协调度超过1018输出”Too hard to arrange””，为防止64位整型运算溢出，可以先用浮点数类型计算，然后再用整型算出具体值。
复杂度分析
状态数为O(N)，每次转移需要以O(N)的时间枚举j，所以时间复杂度为O(N2)。在实际测试中通过了测试点1，2，3，得到30分。
参考程序
?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*
* Problem: NOI2009 poet
* Author: Guo Jiabao
* Time: 2009.9.22 13:30
* State: Solved
* Memo: 朴素动态规划
*/
#include
#include
#include
#include
#include
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值较小，因此可以限制每行长度，以优化状态转移。

实现时应让j从i-1到0枚举，当j2L，则行不协调度(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分。
参考程序
?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/*
* Problem: NOI2009 poet
* Author: Guo Jiabao
* Time: 2009.9.22 13:51
* State: Solved
* Memo: 朴素动态规划 剪枝
*/
#include
#include
#include
#include
#include
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时，观察状态转移方程

设对于F[i]的最优决策为k，那么对于所有的j≠k，均满足

设则有

因为SumL为单调增函数，所以A，B均为增函数。当B[j]>B[k] ??j>k，有

相对的，当j素。求F[i]的最优决策只需不断在队首删除点，直到队首两点组成的直线斜率刚好大于2A[i]，最优决策就是左端点的对应决策。
复杂度分析
用单调队列每次维护凸壳的时间复杂度为均摊O(1)，所以时间复杂度为O(N)。经测试可以通过测试点6，7，配合解法2，一共可以得到70分。
参考程序
?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
/*
* Problem: NOI2009 poet
* Author: Guo Jiabao
* Time: 2009.9.22 14:30
* State: Solved
* Memo: 朴素动态规划 剪枝 凸壳优化
*/
#include
#include
#include
#include
include
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 ij,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 决策单调性优化动态规划
算法描述
可以观察到或证明出，该状态转移方程满足决策单调性。因此我们可以使用双端队列维护每个决策区间，对于每个新决策使用二分查找确定位置并更新决策队列。
算法证明
再次观察状态转移方程

设，状态转移方程可以化为1D/1D标准形式

要证明上述状态转移方程具有决策单调性，k(i)表示F[i]的最优决策，即

当且仅当满足四边形不等式

设，，。其中。
于是。要证明①，只需证明

设，，则②等价于

因为，且D[i+1]恒为正数，所以S在整数域内(非严格)单调递增

(1)若P为偶数
，求导得。
因为，P-1为奇数，所以，恒成立，f(x)在实数域内单调递增。
(2)若P为奇数
(a)当X-C>=0
，求导得。
因为，P-1为偶数，所以，恒成立，f(x)在实数域内单调递增。
(b)当X<=0
，求导得。因为P-1为偶数，恒成立，f(x)在实数域内单调递增。
(c)当0策队列的时间为O(logN)，所以时间复杂度为O(NlogN)。在测试中通过了全部测试点，拿到了100分。
参考程序
?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
/*
* Problem: NOI2009 poet
* Author: Guo Jiabao
* Time: 2009.9.22 16:30
* State: Solved
* Memo: 动态规划 决策单调性
*/
#include
#include
#include
#include
#include
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> 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;
}
相关日志
· NOI 2009 二叉查找树
· NOI 2008 设计路线 design
· NOI 1997 解题报告
· USACO 5.3.1 Milk Measuring 量取牛奶 milk4
· WC2010 能量场
· NOI 2009 解题报告
标签：NOI2009, 优化, 决策单调性, 凸包, 动态规划

24 Responses to “NOI 2009 诗人小G”
1. lccycc Says:
三月 9th, 2010 at 16:37:04
太强悍了!
[回复]
2. lccycc Says:
三月 9th, 2010 at 16:44:04
弱问为什么算法三O(n)的复杂度还过不了全部呢?
[回复]
BYVoid 回复:
三月 9th, 2010 at 18:34:48
算法三是针对第6，7个测试点的特殊算法，算法二可以过了前5个点
[回复]
3. wwy250 Says:
三月 24th, 2010 at 06:11:32
弱问
我知道若满足四边形不等式 一定有决策单调性
但是满足决策单调性一定满足四边形不等式么？
您文中说的是当切仅当
[回复]
BYVoid 回复:

三月 24th, 2010 at 09:03:07
是，参加杨哲论文
[回复]
wwy250 回复:
三月 24th, 2010 at 09:06:23
我有看杨哲论文 没有发现有关于充分必要的结论或证明
[回复]
wwy250 回复:
三月 24th, 2010 at 09:12:00
您能讲解一下么。。。 我自己怎么也推不出来
[回复]
BYVoid 回复:
三月 24th, 2010 at 09:21:15
2007 杨哲《凸完全单调性的一个加强与应用》 幻灯片第三页的证明每一步都是充分必要的
[回复]
wwy250 回复:
三月 24th, 2010 at 09:22:57
可是你用的这个性质在第四页。。。
[回复]
4. Orz Says:
四月 11th, 2010 at 13:25:52
神牛能把这题的数据发给我吗？感激不尽…
[回复]
Orz 回复:
四月 11th, 2010 at 13:26:18

[回复]
BYVoid 回复:
四月 11th, 2010 at 13:36:10

[回复]
Orz 回复:
四月 11th, 2010 at 13:39:13
网上我找过了，就只有day1的另两题的数据，这题是没有的..
[回复]
BYVoid 回复:
四月 11th, 2010 at 15:09:33
好好找找，这题数据50多MB，没办法发
[回复]
5. 哈凌大侠 Says: