경사율 최적화 시리즈 - 훈련 기록

16510 단어

경사율 최적화 훈련 기록


전언


경사율 최적화는 일반적으로 dp의 이동을 최적화하는 데 사용되고 경사율 최적화와 관련된 문제를 훈련하여 DP 사고를 향상시킨다.노선배가 남긴 특집장을 선택하여 연습하는 것은 이 문제의 수가 비교적 많고 개인이 단일한 특집훈련을 장시간 진행하기를 원하지 않기 때문에 이 글을 열어 끊긴 훈련 결과와 소감을 기록한다.

레코드


0x01


간단한 입문 문제인 장난감 포장으로 시작하여 문제의 뜻과 사고방식이 비교적 간단하면 말하지 않겠다.코드
#include
#define dd(x) cout< P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=1e5+10,INF=0x3f3f3f3f,mod=1e9+7;
ll f[maxn],sum[maxn],a[maxn],q[maxn],h,t;
inline double K(int i,int j)
{
    double dy=a[j]*a[j]+f[j]-a[i]*a[i]-f[i],dx=a[j]-a[i];
    return dy/dx;
}
int main()
{
    int n,l;
    cin>>n>>l;
    for (int i=1;i<=n;++i)
    {
        int x;
        scanf("%d",&x);
        sum[i]=sum[i-1]+x;
        a[i]=i+1+sum[i];
    }
    a[0]=1;
    h=t=1;
    for (int i=1;i<=n;++i)
    {
        while (hK(q[t-1],i))
            t--;
        q[++t]=i;
    }
    cout<

0x02

작은 A와 최대 필드 및 입문 문제.문제의 의견은 원제면에서 비교적 간단하다.사고방식은 일반적인 접두사와 사다리꼴 접두사를 유지하고 위와 같이 변형식을 통해 직선 단거리식으로 쓴다.유일한 차이점은 이 문제 Ai가 마이너스일 수 있기 때문에 직선의 경사율은 단조로운 변화를 보장할 수 없기 때문에 가장 좋은 장점을 선택할 때 2분대열이 첫 번째로 직선의 경사율보다 작은 점을 찾아야 한다.(이전 문제는 직선사율이 단조롭게 증가하기 때문에 매번 가장 좋은 점을 선택할 때마다 팀의 첫 번째 직선사율이 적은 점만 모두 팀에 내보내면 된다.)그리고 이 문제는 최대치이기 때문에 입대할 때 상철각을 유지해야 한다.코드
#include
#define dd(x) cout< P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=2e5+10,INF=0x3f3f3f3f,mod=1e9+7;
ll s1[maxn],s2[maxn],q[maxn],h,t;
inline double K(int i,int j)
{
    double dy=j*s1[j]-s2[j]-i*s1[i]+s2[i],dx=j-i;
    return dy/dx;
}
int find(double k)
{
    int l=h,r=t,ans;
    while (l<=r)
    {
        int m=(l+r)>>1;
        if (m==t)
        {
            ans=t;
            break;
        }
        if (K(q[m],q[m+1])<=k)
            ans=m,r=m-1;
        else
            l=m+1;
    }
    return ans;
}
int main()
{
    int n;
    cin>>n;
    for (int i=1;i<=n;++i)
    {
        int x;
        scanf("%d",&x);
        s1[i]=s1[i-1]+x;
        s2[i]=s2[i-1]+i*x;
    }
    ll ans=-1e18;
    h=t=1;
    for (int i=1;i<=n;++i)
    {
        int j=q[find(s1[i])];
        ans=max(ans,s2[i]-s2[j]-j*(s1[i]-s1[j]));
        while (hK(q[t],q[t-1]))
            --t;
        q[++t]=i;
    }
    cout<

0x03

HDU2993이라는 문제는 어렵지 않지만 왜 카드가 읽혀졌는지 구역질이 난다. 로우의 IO 최적화가 비교가 안 된다. 나는 10여 발을 찍은 후에 선배의fread로 읽은 판자를 사용해서 넘겼다.그렇기 때문에 극히 권장하지 않습니다. 뇌 내 AC만 하면 됩니다.제목은 길이가 n인 수열을 주고 길이가 k보다 작지 않고 평균치가 가장 큰 자단을 찾는 것이다.다시 말하면 모든 점(i,sum[i])에서 사율이 가장 큰 두 점의 사율을 찾는 것이다.우리가 하철각을 유지해야 한다는 것은 생각하기 어렵지 않다. (위쪽의 점은 뒤의 점과 더 좋은 해를 구성할 수 없기 때문이다) 그리고 일반적으로 가장 좋은 점을 2분의 1로 나눌 수 있지만 이 문제의 성질로 볼 수 있듯이sum[i]는 점차적으로 증가하기 때문에 매번 더 좋은 점을 찾을 때마다 그 앞의 점은 직접 버릴 수 있다(이것들은 뒤에 새로 추가된 점과 더 큰 사율을 구성할 수 없다).따라서 복잡도는 O (N) 까지 할 수 있다.코드(다시 강조하지만 권장하지 않음)
#include
#define dd(x) cout< P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=1e5+10,INF=0x3f3f3f3f,mod=1e9+7;
struct FastIO {
    static const int S = 1310720;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) { }
    inline int xchar() {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len) pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) return -1;
        return buf[pos++];
    }
    inline int xint() {
        int c = xchar(), x = 0, s = 1;
        if (c==-1)
            return -1;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    ~FastIO() {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;
ll sum[maxn];
int q[maxn],h,t;
inline double K(int i,int j)
{
    return double(sum[i]-sum[j])/(i-j);
}
int main()
{
    int n,k;
    while (n=io.xint(),k=io.xint()) 
    {
        if (n==-1)
            break;
        for (int i=1;i<=n;++i)
        {
            int x=io.xint();
            sum[i]=sum[i-1]+x;
        }
        h=0;
        t=-1;
        double ans=-1;
        for (int i=k;i<=n;++i)
        {
            while (hK(i-k,q[t-1]))
                --t;
            q[++t]=i-k;
            while (h

0x04

HDU 3045, 이동의 합법성을 주의하고 나머지는 일반적인 경사율 최적화 DP이다.특히 경사율의 비교에 있어서 잘못 쓰지 않도록 주의해야 한다(손이 비천할 때 절대값을 얻었고 WA는 십여 발을 얻었다). 정밀도 오차를 피하기 위해 곱셈 형식으로 비교하는 것을 권장한다.코드
#include
#define dd(x) cout< P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=5e5+10,mod=1e9+7,INF=0x3f3f3f3f;
ll a[maxn],sum[maxn],f[maxn];
int q[maxn],h,t;
ll dy(int i,int j)
{
    return f[i]-sum[i]+i*a[i+1]-f[j]+sum[j]-j*a[j+1];
}
ll dx(int i,int j)
{
    return a[i+1]-a[j+1];
}
ll getf(int i,int j)
{
    return f[i]+sum[j]-sum[i]-a[i+1]*(j-i);
}
int main()
{
    int n,k;
    while (scanf("%d%d",&n,&k)!=EOF)
    {
        for (int i=1;i<=n;++i)
            scanf("%I64d",&a[i]);
        sort(a+1,a+1+n);
        for (int i=1;i<=n;++i)
            sum[i]=sum[i-1]+a[i];
        h=t=0;
        for (int i=k;i<=n;++i)
        {
            int j=i-k;
            if (j>=k)
            {
                while (h

0x05

POJ1180, 좋은 문제입니다.문제의 뜻이 비교적 번거롭기 때문에 직접 원제면을 보는 것을 건의합니다.이 문제는 경사율로 최적화된 부분도 매우 일반적이다. 비교적 기교가 있는 것은 매거분조수의 이 단계를 어떻게 최적화하여 복잡도를 O(N)로 낮추는가이다.현재 이 그룹의 종료 시간을 알아야 하기 때문에 이전에 몇 개의 그룹으로 나누어진 것과 관련이 있다. 그러면 이동할 때 반드시 일일이 열거해야 한다.그러나 다른 측면에서 볼 때 우리는 각 그룹이 뒤에 있는 그룹의 대가에 대한 영향을 고려하고 현재 그룹에 초래한 s가 전체 답안에 대한 기여를 미리 계산할 수 있다. 이렇게 이동할 때 앞에 있는 그룹이 현재에 미친 영향을 고려할 필요가 없다(이미 앞에서 계산했기 때문이다).따라서 전이 방정식은 f(j)=min{f(i)+(tsum[j]+s)*(fsum[j]-fsum[i])+s*(fsum[n]-fsum[j])}(0<=i
#include
#include
#include
#define dd(x) cout< P;
const int maxn=1e5+10,mod=1e9+7,INF=0x3f3f3f3f;
ll fsum[maxn],tsum[maxn],dp[maxn];
int q[maxn],h,t,s,n;
inline ll dy(int i,int j)
{
    return dp[i]-dp[j];
}
inline ll dx(int i,int j)
{
    return fsum[i]-fsum[j];
}
inline ll getv(int i,int j)
{
    return dp[i]+(tsum[j]+s)*(fsum[j]-fsum[i])+s*(fsum[n]-fsum[j]);
}
int main()
{
    while (cin>>n)
    {
        cin>>s;
        for (int i=1;i<=n;++i)
        {
            scanf("%lld%lld",&tsum[i],&fsum [i]);
            tsum[i]+=tsum[i-1],fsum[i]+=fsum[i-1];
        }
        t=h=0;
        for (int j=1;j<=n;++j)
        {
            while (h

0x06

HDU 3480으로 쓸 수 있다. 첫 번째 장난감 포장에 비해 그룹 수의 제한이 많고 다른 것은 똑같다.공간의 제한으로, 우리는 매번 대기열을 비우고 다시 사용할 수 있도록 먼저 그룹 수를 열거했다.그룹 수가 k일 때의 답안은 모두 그룹 수 k-1일 때의 답안에서 옮겨진다. 경계점을 주의하고 디테일한 것은 코드
#include
#define dd(x) cout< P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=1e4+10,mod=1e9+7,INF=0x3f3f3f3f;
ll a[maxn],f[maxn>>1][maxn];
int q[maxn],h,t;
inline ll dy(int i,int j,int k)
{
    return f[k][i]+a[i+1]*a[i+1]-f[k][j]-a[j+1]*a[j+1];
}
inline ll dx(int i,int j)
{
    return a[i+1]-a[j+1];
}
inline ll getf(int i,int j,int k)
{
    return f[k-1][i]+(a[j]-a[i+1])*(a[j]-a[i+1]);
}
int main()
{
    int T;
    cin>>T;
    for (int cas=1;cas<=T;++cas)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;++i)
            scanf("%lld",&a[i]);
        sort(a+1,a+1+n);
        for (int j=1;j<=n;++j)
            f[1][j]=(a[j]-a[1])*(a[j]-a[1]);
        for (int k=2;k<=m;++k)
        {
            h=t=0;
            q[0]=k-1;
            for (int j=k;j<=n;++j)
            {
                while (hn?0ll:f[m][n]);
    }
    return 0;
}

0x07

HDU 2829를 참조한다. 이전 문제와 같은 유형이다. 이 문제는 한 구간의 가치를 그 중 임의의 두 개의 곱셈의 합으로 정의한다.구간 가치의 표현식에 있어서 비교적 오래 생각했다. 구간 [i, j]의 가치는 C[j]-C[i]-sum[i]*(sum[j]-sum[i])라고 할 수 있고 C[i]는 접두사 i의 가치를 나타낼 수 있다. 생각해 낸 후에 바로 주제와 같이 처리하고 구덩이가 없으니 경계에 주의하면 된다.코드
#include
#define dd(x) cout< P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=1e3+10,mod=1e9+7,INF=0x3f3f3f3f;
ll f[maxn][maxn],a[maxn],sum[maxn],c[maxn];
int q[maxn],h,t;
inline ll dy(int i,int j,int k)
{
    return f[k][i]+sum[i]*sum[i]-c[i]-f[k][j]-sum[j]*sum[j]+c[j];
}
inline ll dx(int i,int j)
{
    return sum[i]-sum[j];
}
inline ll getf(int i,int j,int k)
{
    return f[k-1][i]+c[j]-c[i]-(sum[j]-sum[i])*sum[i];
}
int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m)&&n)
    {
        ++m;
        for (int i=1;i<=n;++i)
        {
            scanf("%lld",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        for (int i=2;i<=n;++i)
            c[i]=c[i-1]+sum[i-1]*a[i];
        for (int j=1;j<=n;++j)
            f[1][j]=c[j];
        for (int k=2;k<=m;++k)
        {
            h=t=0;
            q[0]=k-1;
            for (int j=k;j<=n;++j)
            {
                while (h

0x08

HDU 3507, 간소화된 장난감 포장은 길이 제한도 그룹 수 제한도 없다. 입문급 코드
#include
#define dd(x) cout< P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=5e5+10,mod=1e9+7,INF=0x3f3f3f3f;
ll f[maxn],a[maxn],sum[maxn];
int q[maxn],h,t,M;
inline ll dy(int i,int j)
{
    return f[i]+sum[i]*sum[i]-f[j]-sum[j]*sum[j];
}
inline ll dx(int i,int j)
{
    return sum[i]-sum[j];
}
inline ll getf(int i,int j)
{
    return f[i]+(sum[j]-sum[i])*(sum[j]-sum[i])+M;
}
int main()
{
    int n;
    while (scanf("%d%d",&n,&M)!=EOF)
    {
        for (int i=1;i<=n;++i)
        {
            scanf("%lld",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        h=t=0;
        for (int i=1;i<=n;++i)
        {
            while (h

0x09

POJ 3709는 길이 제한도 있고 그룹 수 제한도 없다. 일반 해법
#include
#include
#include
#define dd(x) cout< P;
const int maxn=5e5+10,mod=1e9+7,INF=0x3f3f3f3f;
ll f[maxn],a[maxn],sum[maxn];
int q[maxn],h,t,M;
inline ll dy(int i,int j)
{
    return f[i]-sum[i]+i*a[i+1]-f[j]+sum[j]-j*a[j+1];
}
inline ll dx(int i,int j)
{
    return a[i+1]-a[j+1];
}
inline ll getf(int i,int j)
{
    return f[i]+sum[j]-sum[i]-(j-i)*a[i+1];
}
int main()
{
    int T;
    cin>>T;
    while (T--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for (int i=1;i<=n;++i)
        {
            scanf("%lld",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        h=t=0;
        for (int i=k;i<=n;++i)
        {
            int j=i-k;
            if (j>=k)
            {
                while (h

0x0A

HDU 3669는 사람마다 높은 h와 너비 w가 있고 사람은 문을 통과할 수 있다. 높이와 너비가 모두 문보다 크지 않다.k문을 초과하지 않으려면 모든 문이 하나의 W와 H를 확정하고 모든 문의 제조비는 W*H로 모든 사람이 최소한의 문을 통과하여 최소한의 제조비를 구할 수 있다.계산을 편리하게 하기 위해 우리는 일정한 예처리를 한다. 우리는 사람의 한 속성 승차순에 따라 배열하고 얻은 서열은 다른 속성 승차순에 따라 배열한다(즉 h와 w가 모두 누군가보다 작은 사람을 제거하면 분명히 그들은 답안에 영향을 주지 않는다). 이때 얻은 서열은 1차원 증가, 2차원 감소를 만족시킨다.분명히 같은 문에 들어간 사람은 서열에서 틀림없이 연속된 것이다.DP를 하나 달려서 조를 나누면 경사율이 최적화되고 전이가 끝난다.예처리 디테일 코드
#include
#define fi first
#define se second
#define dd(x) cout< P;
const int maxn=5e4+10;
P a[maxn];
int q[maxn],h,t;
ll f[200][maxn];
inline ll dy(int i,int j,int k)
{
    return f[k][i]-f[k][j];
}
inline ll dx(int i,int j)
{
    return -a[i+1].se+a[j+1].se;
}
inline ll getf(int i,int j,int k)
{
    return f[k-1][i]+a[i+1].se*a[j].fi;
}
int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        for (int i=1;i<=n;++i)
            scanf("%lld%lld",&a[i].fi,&a[i].se);
        sort(a+1,a+1+n);
        int cnt=0;
        for (int i=1;i<=n;++i)
        {
            while (cnt&&a[i].se>=a[cnt].se)
                --cnt;
            a[++cnt]=a[i];
        }
        m=min(m,cnt);
        for (int i=1;i<=cnt;++i)
            f[1][i]=a[i].fi*a[1].se;
        for (int k=2;k<=m;++k)
        {
            h=t=0;
            q[0]=k-1;
            for (int j=k;j<=cnt;++j)
            {
                while (h

0x0B

311B-Cats Transport, 아주 좋은 문제입니다. 고양이마다 가장 먼저 출발하는 시간ai를 처리해야 합니다. 이 시간의 순서에 대해 욕심을 내면 모든 사육사가 연속적인 고양이를 책임져야 한다는 것을 알 수 있습니다.그래서 이 수조 a에 대해 dp로 그룹을 나누고 경사율을 최적화한다.
#include
#define dd(x) cout< P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=1e5+10,mod=1e9+7,INF=0x3f3f3f3f;
ll a[maxn],f[105][maxn],sumd[maxn],suma[maxn]; 
int q[maxn],h,t;
ll dy(int i,int j,int k)
{
    return f[k][i]+suma[i]-f[k][j]-suma[j];
}
ll dx(int i,int j)
{
    return i-j;
}
ll getf(int i,int j,int k)
{
    return f[k-1][i]+a[j]*(j-i)-suma[j]+suma[i];
}
int main()
{
    int n,m,p;
    cin>>n>>m>>p;
    for (int i=2;i<=n;++i)
    {
        scanf("%I64d",&sumd[i]);
        sumd[i]+=sumd[i-1];
    }
    for (int i=1;i<=m;++i)
    {
        ll h,t;
        scanf("%I64d%I64d",&h,&t);
        a[i]=t-sumd[h];
    }
    sort(a+1,a+1+m);
    for (int i=1;i<=m;++i)
    {
        suma[i]=suma[i-1]+a[i];
        f[1][i]=i*a[i]-suma[i];
    }
    for (int k=2;k<=p;++k)
    {
        h=t=0;
        q[0]=k-1;
        for (int j=k;j<=m;++j)
        {
            while (h

0x0C

화폐 교환 캐시는 욕심이 많은 사상에서 알 수 있듯이 매번 매매할 때마다 반드시 돈을 다 쓰거나 금권을 다 팔 것이다.따라서 f(i)는 i일째 수중에 최대 얼마가 있는지 표시하고, f(i)=max(A(j)*a[i]+B(j)*b[i])는 A(j)는 j일째 돈을 다 쓰면 받을 수 있는 A금권 수량을 표시하며, B(j)는 같은 이치다.약간 변형된 -B(j)=a[i]/b[i]*A(j)-f[i]/b[i].가로 좌표 A(j)와 사율 a[i]/b[i]가 단조롭지 않은 것을 발견할 수 있다.이런 상황은 균형 트리 유지보수 동적 볼륨이나 cdq분할로 해결할 수 있다.나는 이 문제를 해결하기 위해 CDQ를 선택했다.대개 사상은 모든 f(i)에 대해 그의 결정점은 반드시 그의 왼쪽에 있다는 것이다. 다시 말하면 모든 점은 그의 오른쪽의 점에만 영향을 줄 뿐이다.구해구간 [l, r] 내의 f값에 대해 먼저 그 왼쪽 구간을 귀속시켜 구해할 수 있다. 완성된 후 왼쪽 구간의 f는 처리된 다음에 왼쪽 구간의 점에 대해 다시 정렬하여 돌출된 가방을 유지한다. 오른쪽 구간의 점에 대해 이 돌출된 가방을 2분으로 나누어 결정점을 찾아 업데이트한 다음에 오른쪽 구간 내부의 영향을 귀속시켜 구해한 다음에 완성된 후에 오른쪽 구간의 f값도 처리된다.이 때 이 구간의 f값이 처리되었습니다.
#include
#define dd(x) cout< P;
typedef priority_queue pq;
const int maxn=1e5+10,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-8;
double a[maxn],b[maxn],r[maxn],f[maxn];
int tmp[maxn],q[maxn],t;
inline int sign(double x){
    if (fabs(x)1&&sign(dy(i,q[t-1])*dx(q[t],q[t-1])-dy(q[t],q[t-1])*dx(i,q[t-1]))<=0)
        --t;
    q[++t]=i;
}
double find(int i)
{
    double k=a[i]/b[i];
    int l=1,r=t,p;
    while (l<=r)
    {
        int m=(l+r)>>1;
        if (m==t)
        {
            p=t;
            break;
        }
        if (sign(dy(q[m+1],q[m])-k*dx(q[m+1],q[m]))>=0)
            p=m,r=m-1;
        else
            l=m+1;
    }
    return A(q[p])*a[i]-B(q[p])*b[i];
}
void cdq(int l,int r)
{
    if (l==r)
    {
        f[l]=max(f[l],f[l-1]);
        return;
    }
    int m=(l+r)>>1;
    cdq(l,m);
    int tn=0;
    for (int i=l;i<=m;++i)
        tmp[tn++]=i;
    sort(tmp,tmp+tn,cmp);
    t=0;
    for (int i=0;i>n>>s;
    for (int i=1;i<=n;++i)
        scanf("%lf%lf%lf",&a[i],&b[i],&r[i]);
    f[1]=s;
    cdq(1,n);
    printf("%.3lf",f[n]);
    return 0;
}
Swift에서 Int형 switch case의 트랩(?)
클래스를 사용하여 트위터 API 모듈 만들기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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