Cjj神最近发出N局预约的排位赛。第i到底木棍的尺寸为Li

WZRY

1044: [HAOI2008]木棍分割

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 4281  Solved: 1644
[Submit][Status][Discuss]

为了排位赛的Cjj神,最近耗尽气力来打WZRY。

Description

  有n根木棍, 第i完完全全木棍的长短也Li,n根木棍依次连结了并,
总共有n-1单连续处. 现在同意而尽多砍断m个连
接处, 砍完后n根木棍被分为了众多段,要求满足总长度最要命之同一段子长最小,
并且输出有略种砍的点子使得总长
过尽酷的一致段落长度最小. 并以结果mod 10007。。。

Cjj神最近有N局预约的排位赛,其中第i局需要耗时Li的日。因为浓浓的Gay情,Cjj神不能够改这些排位赛的的顺序。作为一个死有(mei)自制力的人,Cjj神计划用M+1天从了结N局,为了能够活在见到第M+2龙之阳光,他愿意耗时极度丰富的一样上最为缺。

Input

  输入文件首先实践有2独数n,m.接下来n行每行一个正整数Li,表示第i根本木棍的长度.n<=50000,0<=m<=min(n-1,10
00),1<=Li<=1000.

每天最好少打一商行。

Output

  输出有2单数, 第一个数是究竟长度最充分之同段的尺寸最小价,
第二个数是发生多少种砍的法子让满足条件.

请报告他这价是不怎么,以要他判断他是不是会生存下来;并且告诉他于总时长太丰富平龙等是极度小值的场面下出略种方案,以要他判断他生下来的几率是略。

Sample Input

3
2
1
1
10

输入格式

Sample Output

10
2

先是执两个整数N,M。

HINT

鲜栽砍的方式: (1)(1)(10)和(1 1)(10)

引人注目我们得以二区划算有第一叩问

算是有第一叩后,我们便可dp求方案往往了

设f[i][j]意味着前i个木棒割j刀的方案往往

则f[i][j] = ∑f[k][j – 1]  【k <
i 且 sum[i] – sum[k] <= mx】

然这么做会爆

第一我们好滚动数组,空间不爆了

其次我们见面意识sum是与日俱增的,也就是说k可以k

  • 1 ~ i – 1一定还得以,我们每次维护一浅f的前缀和就可加快了

【注意:取模过程中关系减法,最后答案输出时如果取回正数】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 50005,maxm = 1005,INF = 1000000000,P = 10007;
inline int RD(){
    int out = 0,flag = 1; char c = getchar();
    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
    while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}
    return out * flag;
}
int n,m,f[2][maxn],A[maxn],sum[maxn],S[maxn],mx = 0,Sum = 0,ans = 0;
bool check(int M){
    if (mx > M) return false;
    int cnt = 0,tot = 0;
    for (int i = 1; i <= n; i++){
        if (tot + A[i] > M) cnt++,tot = 0;
        tot += A[i];
        if (cnt > m) return false;
    }
    return true;
}
int main(){
    n = RD(); m = RD();
    REP(i,n) A[i] = RD(),sum[i] = sum[i - 1] + A[i],mx = max(mx,A[i]);
    int l = 1,r = sum[n],mid;
    while (l < r){
        mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout<<(mx = l)<<' ';
    f[0][0] = 1;
    for (int k = 0,p = 0; k <= m; k++){
        S[0] = f[p][0];
        REP(i,n) S[i] = (S[i - 1] + f[p][i]) % P;
        p ^= 1; int pos = 0;
        f[p][0] = 0;
        for (int i = 1; i <= n; i++){
            /*
            for (int j = i - 1; j > 0; j--)
                if (sum[i] - sum[j] <= mx)
                    f[p][i] = (f[p][i] + f[p ^ 1][j]) % P;
                else break;*/
            while (sum[i] - sum[pos] > mx) pos++;
            f[p][i] = (S[i - 1] - (pos ? S[pos - 1] : 0)) % P;
        }
        ans = (ans + f[p][n]) % P;
    }
    cout<<(ans + P) % P<<endl;
    return 0;
}

接下来N个整数Li。

输出格式

无异于实行两独数,第一独凡是总时长太丰富之一模一样上的极度小价,第二单数是方案总数,对10,007取模。

数据范围

10%:N<=25

30%:N<=300

60%:N<=10000

100%:N<=50000,0<=m<
n,m<1000,1<=Li<=1000

 

当时道题出零星叩问,第一叩问得老简单地用二细分+贪心解决。

可第二问问也?

首先就道题的一般性暴力DP是甚好想到的,设f[i][j]否第i天,打了j局较量之方案总数。

很显然f[i][j]=∑f[i-1][k](sum[j]-sum[k]<=ans)

sum为Li的前缀和。

纳上暴力代码:

365体育官网 1365体育官网 2

#include <bits/stdc++.h>
#define mod 10007
using namespace std;
inline char tc(){
    static char fl[100000],*A=fl,*B=fl;
    return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline int read(){
    char c;
    while(!isdigit(c=tc()));int x=c-'0';
    while(isdigit(c=tc()))x=x*10+c-'0';
    return x;
}
int n,m,a[30001],mx,ans,ww,f[1001][30001],sum[30001];
int check(int x){
    int tot=0,last=x,d=1;
    for(int i=1;i<=n;i++)
        if(last>=a[i])last-=a[i];
        else d++,last=x-a[i];
    return d<=m;
}
int main(){
    n=read(),m=read();m++;
        for(int i=1;i<=n;i++)a[i]=read(),mx=max(mx,a[i]),ww+=a[i],sum[i]=sum[i-1]+a[i];
    int L=mx,R=ww;
        while(L<=R){
            int mid=L+R>>1;
            if(check(mid))R=mid-1,ans=mid;
            else L=mid+1;
        }//二分,第一问
        for(int i=1;i<=m;i++){f[i-1][0]=1;
            for(int j=i;j<=n;j++){
                for(int k=i-1;k<j;k++)
                    if(sum[j]-sum[k]<=ans)
                    f[i][j]=(f[i][j]+f[i-1][k])%mod;
            }
        }
    int tot=0;
        for(int i=1;i<=m;i++)tot=(tot+f[i][n])%mod;
    printf("%d %d",ans,tot);
}

暴力

这个O(M*N^2)的效率肯定会过,所以我们要对暴力优化。

细看是暴力,不难发现实际是一个未鸣金收兵枚举j和k边界的经过。

再者想到我们明白最酷耗时底极致小值,那么就是可以在已经知道k便边界的气象下通过预处理求出j边界的价值。

设pre[i]表示第i局最远可由哪一样店家转移过来。

那么单纯待枚举k加前缀和保障f数组的价就是好得到O(MN)的算法了。

而是通过观察数据可得内存会炸,由于生前缀和护卫,只待每次i做得了1不行时以f清零即可。

code:

365体育官网 3365体育官网 4

#include <bits/stdc++.h>
#define mod 10007
#define ll long long
using namespace std;
inline char tc(){
    static char fl[100000],*A=fl,*B=fl;
    return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline int read(){
    char c;
    while(!isdigit(c=tc()));int x=c-'0';
    while(isdigit(c=tc()))x=x*10+c-'0';
    return x;
}
int n,m,a[30001],mx,ans,ww,f[30001];
int sum[30001],pre[30001],d[30001];
int check(int x){
    int tot=0,last=x,d=1;
    for(int i=1;i<=n;i++)
        if(last>=a[i])last-=a[i];
        else d++,last=x-a[i];
    return d<=m;
}
int main(){
    n=read(),m=read();m++;
        for(int i=1;i<=n;i++)a[i]=read(),mx=max(mx,a[i]),ww+=a[i],sum[i]=sum[i-1]+a[i];
    int L=mx,R=ww;
        while(L<=R){
            int mid=L+R>>1;
            if(check(mid))R=mid-1,ans=mid;
            else L=mid+1;
        }
        for(int i=1;i<=n;i++){int sum=0;
            for(int j=i;j>0;j--){
                if(sum+a[j]<=ans)sum+=a[j];
                else {pre[i]=j;break;}
            }
        }//预处理pre
        for(int i=0;i<=n;i++)d[i]=1;
    int tot=0;
        for(int i=1;i<=m;i++){
            for(int j=i;j<=n;j++){
                if(pre[j]>0)f[j]=(f[j]+d[j-1]-d[pre[j]-1])%mod;
                else f[j]=(f[j]+d[j-1])%mod;
            }d[0]=0;
            tot=(tot+f[n])%mod;
            for(int j=1;j<=n;j++)d[j]=(d[j-1]+f[j])%mod,f[j]=0;//维护,清零
        }
    tot=((tot+mod)%mod+mod)%mod; 
    printf("%d %d",ans,tot);
}

AC