程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva live 6190 Beautiful Spacing （二分+dp檢驗根據特有性質優化）

uva live 6190 Beautiful Spacing （二分+dp檢驗根據特有性質優化）

編輯：C++入門知識

uva live 6190 Beautiful Spacing （二分+dp檢驗根據特有性質優化）

I - Beautiful Spacing Time Limit:8000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu Submit Status

Description

Text is a sequence of words, and a word consists of characters. Your task is to put words into a grid with W columns and sufficiently many lines. For the beauty of the layout, the following conditions have to be satisfied.

The words in the text must be placed keeping their original order. The following figures show correct and incorrect layout examples for a 4 word text "This is a pen" into 11 columns.

Figure I.1: A good layout.

Figure I.2: BAD " Do not reorder words.

Between two words adjacent in the same line, you must place at least one space character. You sometimes have to put more than one space in order to meet other conditions.

Figure I.3: BAD " Words must be separated by spaces.

A word must occupy the same number of consecutive columns as the number of characters in it. You cannot break a single word into two or more by breaking it into lines or by inserting spaces.

Figure I.4: BAD " Characters in a single word must be contiguous.

The text must be justified to the both sides. That is, the first word of a line must startfrom the first column of the line, and except the last line, the last word of a line must end at the last column.

Figure I.5: BAD " Lines must be justi ed to both the left and the right sides.

The text is the most beautifully laid out when there is no unnecessarily long spaces. For instance, the layout in Figure I.6 has at most 2 contiguous spaces, which is more beautiful than that in Figure I.1, having 3 contiguous spaces. Given an input text and the number of columns, please find a layout such that the length of the longest contiguous spaces between words is minimum.

Figure I.6: A good and the most beautiful layout.

Input

The input consists of multiple datasets, each in the following format.<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+ICAgIDxlbT5XIE48YnI+CiAgICB4PC9lbT48c3ViPjE8L3N1Yj48ZW0+eDwvZW0+PHN1Yj4yPC9zdWI+IC4uLiA8ZW0+eDxzdWI+Tjwvc3ViPjwvZW0+PGJyPgo8L3A+CjxwPjxlbT5XPC9lbT4sIDxlbT5OPC9lbT4sIGFuZCA8ZW0+eDxzdWI+aTwvc3ViPjwvZW0+IGFyZSBhbGwgaW50ZWdlcnMuIDxlbT5XPC9lbT4gaXMgdGhlIG51bWJlciBvZiBjb2x1bW5zICgzIKHcIDxlbT5XPC9lbT4godwgODAsMDAwKS4gPGVtPk48L2VtPiBpcyB0aGUgbnVtYmVyIG9mIHdvcmRzICgyIKHcIDxlbT5OPC9lbT4godwgNTAsMDAwKS4gPGVtPng8c3ViPmk8L3N1Yj48L2VtPiBpcyB0aGUgbnVtYmVyIG9mIGNoYXJhY3RlcnMgaW4gdGhlIDxlbT5pPC9lbT4tdGgKIHdvcmQgKDEgodwgPGVtPng8c3ViPmk8L3N1Yj48L2VtPiCh3CAoPGVtPlc8L2VtPj8xKS8yICkuIE5vdGUgdGhhdCB0aGUgdXBwZXIgYm91bmQgb24gPGVtPng8c3ViPmk8L3N1Yj48L2VtPiBhc3N1cmVzIHRoYXQgdGhlcmUgYWx3YXlzIGV4aXN0cyBhIGxheW91dCBzYXRpc2Z5aW5nIHRoZSBjb25kaXRpb25zLjwvcD4KPHA+VGhlIGxhc3QgZGF0YXNldCBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyB0d28gemVyb3MuPC9wPgo8aDI+T3V0cHV0PC9oMj4KPHA+Rm9yIGVhY2ggZGF0YXNldCwgcHJpbnQgdGhlIHNtYWxsZXN0IHBvc3NpYmxlIG51bWJlciBvZiB0aGUgbG9uZ2VzdCBjb250aWd1b3VzIHNwYWNlcyBiZXR3ZWVuIHdvcmRzLjwvcD4KPGgyPlNhbXBsZSBJbnB1dDwvaDI+CjxwcmUgY2xhc3M9"brush:java;">11 4 4 2 1 3 5 7 1 1 1 2 2 1 2 11 7 3 1 3 1 3 3 4 100 3 30 30 39 30 3 2 5 3 0 0

Output for the Sample Input

題意：給你一個含n個單詞的文本，按照一些規則放入寬度為w的矩形中，怎樣使最大的空格最小。思路：答案是單調的，二分答案，然後用dp來檢驗，dp[i]表示第i個單詞能否結尾，容易想到的是n^2檢驗，但是肯定會TLE的，需要優化。可以發現如果i-j能夠放在一行，但是最大空格會超過mid，那麼i+1-j也不行，如果用i來推的時候能夠推到[s,t]可以，那麼下次就可以直接從t+1開始了。代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define maxn 50005
#define MAXN 200005
#define mod 1000000007
#define INF 0x3f3f3f3f
#define eps 1e-6
const double pi=acos(-1.0);
typedef long long ll;
using namespace std;

int n,w;
int len[maxn],sum[maxn];
bool dp[maxn];

bool isok(int mid)
{
    int i,j,last=0;
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    if(sum[n]+n-1<=w) return true ;
    for(i=0; isum[j]-sum[i]+ll(j-i-1)*mid) continue ;
            last=j;
            dp[j]=1;
            if(sum[n]-sum[j]+n-j-1<=w) return true ;
        }
    }
    return false ;
}
void solve()
{
    int i,j,le=1,ri=w,mid,ans;
    while(le<=ri)
    {
        mid=(le+ri)>>1;
        if(isok(mid))
        {
            ans=mid;
            ri=mid-1;
        }
        else le=mid+1;
    }
    printf("%d\n",ans);
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&w,&n))
    {
        if(w==0&&n==0) break ;
        sum[0]=0;
        for(i=1; i<=n; i++)
        {
            scanf("%d",&len[i]);
            sum[i]=sum[i-1]+len[i];
        }
        solve();
    }
    return 0;
}