w****x
发帖数: 2483 | 1 Print neatly
一下忘了怎么做了，花了半小时，处理下标很痛苦啊。
忽然发现没想的那么复杂。
//you have a list of words, you want to print them
//on a paper with width n. when printing, each
//word must be separated by one blank except the blanks after the last word.
Find the fewest
//possible blanks except the last line.
//f(i, j) = [1 + f(i+1, j+len(i)+1) ] || [nLen - j-len(i) + f(i+1,0)]
int GetLeastBlanks(int a[], int n, int nLen)
{
if (NULL == a || n <= 0 || nLen <= 0)
return -1;
int rec[100][100] = { 0 };
for (int i = n-2; i >= 0; i--)
{
for (int j = nLen-1; j >= 0; j--)
{
if (j + a[i] > nLen)
continue;
int nStartLine = nLen - j - a[i] + rec[i+1][0];
int nCont = INT_MAX;
if (j + a[i] + a[i+1] < nLen)
nCont = 1 + rec[i+1][j+a[i]+1];
rec[i][j] = min(nStartLine, nCont);
}
}
return rec[0][0];
} | H****s
发帖数: 247 | 2 牛啊， 这题看着很难的样子！真的是面试题吗？
你的公式里 i, j各是什么啊？
word.
【在 w****x 的大作中提到】
: Print neatly
: 一下忘了怎么做了，花了半小时，处理下标很痛苦啊。
: 忽然发现没想的那么复杂。
: //you have a list of words, you want to print them
: //on a paper with width n. when printing, each
: //word must be separated by one blank except the blanks after the last word.
: Find the fewest
: //possible blanks except the last line.
: //f(i, j) = [1 + f(i+1, j+len(i)+1) ] || [nLen - j-len(i) + f(i+1,0)]
: int GetLeastBlanks(int a[], int n, int nLen)
| w****x
发帖数: 2483 | 3
i是第几个单词，j是第几列
【在 H****s 的大作中提到】
: 牛啊， 这题看着很难的样子！真的是面试题吗？
: 你的公式里 i, j各是什么啊？
:
: word.
| c********t
发帖数: 5706 | 4 是Text Justification吗？一道我做吐血的题
word.
【在 w****x 的大作中提到】
: Print neatly
: 一下忘了怎么做了，花了半小时，处理下标很痛苦啊。
: 忽然发现没想的那么复杂。
: //you have a list of words, you want to print them
: //on a paper with width n. when printing, each
: //word must be separated by one blank except the blanks after the last word.
: Find the fewest
: //possible blanks except the last line.
: //f(i, j) = [1 + f(i+1, j+len(i)+1) ] || [nLen - j-len(i) + f(i+1,0)]
: int GetLeastBlanks(int a[], int n, int nLen)
| w****x
发帖数: 2483 | 5
好像有这么一个同名的题
【在 c********t 的大作中提到】
: 是Text Justification吗？一道我做吐血的题
:
: word.
| p*g
发帖数: 141 | 6 is it the same as least number of lines?
word.
【在 w****x 的大作中提到】
: Print neatly
: 一下忘了怎么做了，花了半小时，处理下标很痛苦啊。
: 忽然发现没想的那么复杂。
: //you have a list of words, you want to print them
: //on a paper with width n. when printing, each
: //word must be separated by one blank except the blanks after the last word.
: Find the fewest
: //possible blanks except the last line.
: //f(i, j) = [1 + f(i+1, j+len(i)+1) ] || [nLen - j-len(i) + f(i+1,0)]
: int GetLeastBlanks(int a[], int n, int nLen)
| p*****2
发帖数: 21240 | 7
这个是不是greedy就可以了？
【在 p*g 的大作中提到】
: is it the same as least number of lines?
:
: word.
| H****s
发帖数: 247 | 8 好像不是同一个题
【在 c********t 的大作中提到】
: 是Text Justification吗？一道我做吐血的题
:
: word.
|
|
|
