学步园

这道题卡了我们整场，我们想到了二分答案+判断可行性，但是卡在判断可行性上了，首先n^2的复杂度是肯定不行的，正解要优化到O(n)

dp[i]表示以第i个单词作为一行结尾是否可行，初始化dp[0]=1,然后是一个迭代的过程，由dp[i]推出一个区间可行解dp[left~right]=1;接下来从left+1推出下一个区间可行解，最后在加点判断即可。注意要在整个过程中维护一个变量k表示当前最大的满足dp[i]=1的i=k来保证算法是o(n)的。

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

#define mxn 50005
#define LL long long

int a[mxn];
LL s[mxn];
bool v[mxn];
int w, n;

bool check( int d ){
    memset( v, 0, sizeof(v) ); v[0] = 1;
    int k = 0;
    for( int i = 1; i <= n; ++i ){
        if(v[n]) return true;
        if( v[i-1] == false ) continue;
        for( int j = k + 1; j <= n; ++j ){
            if( j==i ) continue;
            LL sum = s[j] - s[i-1];
            if( sum-1 > w ) break;
            int tem ;
            if((w-sum+j-i+1)%(j-i)!=0)
                tem=1;
            else tem=0;
            tem+=(w-sum+j-i+1)/(j-i);
            if( tem <= d ){
                k = max( k, j );
                v[j] = 1;
            }
        }
    }
    for( int i = n; i >= 0; --i ){
        int sum = s[n] - s[i-1];
        if( sum -1> w ) break;
        if( v[i-1] ) return true;
    }
    if( v[n] ) return true;
    return false;
}

int main()
{
    while( scanf( "%d%d", &w, &n ) == 2 && w ){
        for( int i = 1; i <= n; ++i )
            scanf( "%d", a + i ), ++a[i];
        s[0] = 0;
        for( int i = 1; i <= n; ++i )
            s[i] = s[i-1] + a[i];
        int l = 1, ans,r = w;
        while( l <= r ){
            int m = ( l + r ) >> 1;
            if( check(m) ){
                ans=m;
                r = m-1;
            }
            else l = m + 1;
        }
        printf( "%d\n", ans );
    }
    return 0;
}