[BZOJ1044] [HAOI2008] 막대기 분할(2점+욕심+dp)

제목 설명

전송문
제목의 뜻: n개의 나무 막대기가 있고, i개의 나무 막대기의 길이는 리이며, n개의 나무 막대기는 순서대로 연결되어 총 n-1개의 연결부분이 있다.현재 최대 m개의 연결부를 잘라낼 수 있습니다. 베어낸 후 n개의 나무 막대기는 여러 단락으로 나뉘어져 있습니다. 총 길이가 가장 큰 단락의 길이를 충족시키고 몇 가지 베어내는 방법을 출력하여 총 길이가 가장 큰 단락의 길이를 최소화해야 합니다.결과mod 10007을 생성합니다.

문제풀이

첫 번째 질문은 욕심+2점 판정으로 답을 판정한 후 dp로 한 번 묻는다. f(i, j)는 i칼을 베었다는 뜻으로 j번째 방안수를 베었다. 단조롭게 한 번 훑어보고 i번째 위치가 가장 먼 곳에서 어디로 이동할 수 있는지 미리 처리한 다음에 접두사와 최적화+스크롤 그룹을 사용하면 된다.

코드

#include
#include
#include
#include
#include
using namespace std;
#define Mod 10007
#define N 50005

int n,m,Max,Min,ans1,ans2;
int a[N],sa[N],last[N],f[2][N],s[2][N];

bool check(int mid)
{
    int now,cnt=0;
    for (int i=0,j;i<=n;i=j)
    {
        j=i;now=0;
        while (j<=n&&now+a[j]<=mid)
            now+=a[j],++j;
        ++cnt;
    }
    return cnt<=m+1;
}
int find()
{
    int l=Min,r=Max,mid,ans;
    while (l<=r)
    {
        mid=(l+r)>>1;
        if (check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);sa[i]=sa[i-1]+a[i];
        Max+=a[i],Min=max(Min,a[i]);
    }
    ans1=find();
    int p=0;
    for (int i=1;i<=n;++i)
    {
        while (sa[i]-sa[p]>ans1) ++p;
        last[i]=p;
        if (!last[i]) f[1][i]=1;
    }
    for (int i=1;i<=n;++i) s[1][i]=(s[1][i-1]+f[1][i])%Mod;
    for (int i=2;i<=m+1;++i)
    {
        memset(f[i&1],0,sizeof(f[i&1]));
        memset(s[i&1],0,sizeof(s[i&1]));
        for (int j=i;j<=n;++j)
        {
            f[i&1][j]=(f[i&1][j]+s[(i-1)&1][j-1])%Mod;
            if (last[j]) f[i&1][j]=(f[i&1][j]-s[(i-1)&1][last[j]-1]+Mod)%Mod;
            s[i&1][j]=(s[i&1][j-1]+f[i&1][j])%Mod;
        }
        ans2=(ans2+f[i&1][n]);
    }
    printf("%d %d
",ans1,(ans2+Mod)%Mod);
}