[분치 결정 단순성 최적화 DP] LOJ#6039.'아례 합숙 2017 Day 5'보석

fi,jfi,j를 설정하면 판매가≤i≤i의 보석을 표시하고 jj만 위안의 최대 흡인력을 사용합니다.전이 방정식은 쓰기 쉽다.같은 가격의 보석은 틀림없이 가장 큰 흡인력에서 시작된 것이기 때문에 이동하는 함수는 상철이다.jj를 jmod i jm o d i로 분류하고 각 유형의 이동은 의사결정의 단조성을 만족시킨 다음에 분치로 할 수 있다.시간 복잡도 O(maxciklogk) O(m a x c i k log ⁡k)는 실제 복잡도가 이 값보다 훨씬 작다.

#include
using namespace std;
char nc() {
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
void Read(int& x) {
    char c=nc();
    for(;c<'0'||c>'9';c=nc());
    for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
}
typedef long long ll;
const int N=50010;
int k,n,m,mx,x,y,num;
ll f[N],h[N];
vector<int>g[310];
ll s[1000010];
bool b;
bool Cmp(ll x,ll y) {
    return x>y;
}
void Solve(int x,int y,int l,int r,int L,int R) {
    if(l>r) return;
    int Mid=l+r>>1,pos=L;ll mx=0;
    for(int i=max(L,Mid-num);i<=R&&i<=Mid;i++)
        if(f[(i-1)*x+y]+s[Mid-i]>=mx) mx=f[(i-1)*x+y]+s[Mid-i],pos=i;
    h[(Mid-1)*x+y]=mx;
    Solve(x,y,l,Mid-1,L,pos);Solve(x,y,Mid+1,r,pos,R);
}
int main() {
    Read(n);Read(m);
    for(int i=1;i<=n;i++) Read(x),Read(y),g[x].push_back(y),mx=max(mx,x);
    for(int i=1;i<=mx;i++) 
        if(g[i].size()) {
            sort(g[i].begin(),g[i].end(),Cmp);
            num=g[i].size();
            for(int j=0;j1]=s[j]+g[i][j];
            for(int j=0;jint cnt=0;
                for(int k=j;k<=m;k+=i) cnt++;
                Solve(i,j,1,cnt,1,cnt);
                for(int k=j;k<=m;k+=i) f[k]=h[k];
            }
        }
    for(int i=1;i<=m;i++) printf("%lld ",f[i]);
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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