나무 막대기 분할(dp+2점 정답+욕심)

5126 단어 2점 답안bzoj탐욕스럽다
우선 우리 2점 답안+욕심으로 첫 번째 질문에 대한 답안ans.그리고 dp는 방안수를 구한다. f[i][j]는 전 i근이 j단으로 나뉘어진 방안수를 나타낸다. 우리는 분명히 O(n2k)의 dp가 있다.최적화를 고려하면 우리가 매번 이동할 때마다 실제적으로 구간의 합이고 이 구간이 단조롭고 오른쪽으로 이동하기 때문에 우리는 바늘로 이동을 최적화할 수 있다. 복잡도 O(nk) 다음에 그룹을 굴려야 한다.
#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 50010
#define mod 10007
inline char gc(){
    static char buf[1<<16],*S,*T;
    if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
    return x*f;
}
int n,m,a[N],f[N][2],ans,tot=0;//f[i][j], i   j     
inline bool jud(int x){
    int res=0,sum=0;
    for(int i=1;i<=n;++i){
        if(a[i]>x) return 0;
        if(sum+a[i]>x) ++res,sum=0;
        sum+=a[i];
    }return res<=m;
}
int main(){
//  freopen("a.in","r",stdin);
    n=read();m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    int l=1,r=5e7;
    while(l<=r){
        int mid=l+r>>1;
        if(jud(mid)) r=mid-1;
        else l=mid+1;
    }ans=r+1;f[0][0]=1;int sum=0,tmp=0;++m;int p=0;
    for(int j=1;j<=m;++j){
        sum=0;l=0;tmp=0;
        for(int i=0;i<=n;++i){
            sum+=a[i];while(sum-a[l]>ans) sum-=a[l],tmp-=f[l][p],++l;
            f[i][p^1]=tmp%mod;tmp+=f[i][p];
        }p^=1;tot=(tot+f[n][p])%mod;
    }printf("%d %d
",ans,tot);
    return 0;
}
[낙곡P1373] [문제풀이] 작은 a와 uim의 대탈출.
Windows+Python 3.8에서 sphinx-autobuild 202.9.1을 사용하기 위해

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage