Codeforces 309B Context Advertising 题解
题意
给定$n,r,c$和一个由$n$个单词组成的句子(两两单词之间有一个空格),在这个句子里选出若干个连续的单词,组成一个“矩阵”,行数不能超过$r$,每行字符数不能超过$c$(包括空格),不能把一个单词拆开。求合法矩阵中,单词数最多的那个矩阵,并输出。
题解
题目要求组成一个$r\times c$的矩阵。
- 先考虑每行字符数的这个条件。设这个句子为$s_0,s_1,\dots,s_{n-1}$,对于一个单词$i(0\le i< n)$,找出一个最大的$j(i<j\le n)$,满足$|s_i|+|s_{i+1}|+\dots+|s_{j-1}|+(j-i-1)\le c$,从$i$到$j$连一条无向边。这个过程可以用双指针或二分完成。这样,就构造了一棵树。
- 再考虑行数这个条件。对于树上每个结点$i$,用倍增求出它的$r$辈祖先$j$,那么这若干个连续单词的长度是$j-i$。找出最大长度,输出即可。
程序(双指针+倍增)
1 | // #pragma GCC optimize(2) |