LOJ

LOJ

关注
发信
关注(28)粉丝(399)

YBT 5.1 区间类动态规划

题解在代码中

石子合并[loj 10147]

/*

dp[i][j]=max or min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])

i<=k<j

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

int a[],n,dp_minn[][],dp_maxn[][],sum[];

int main()

{

    memset(dp_minn,,sizeof(dp_minn));

    n=read();

    for(int i=;i<=n;i++)

    {

        dp_minn[i][i]=dp_minn[i+n][i+n]=;

        a[i]=read(),a[i+n]=a[i];

    }

    for(int i=;i<=*n;i++) sum[i]=sum[i-]+a[i];

    for(int t=;t<=n;t++)

        for(int i=;i<=*n&&i+t-<=*n;i++)

        {

            int j=i+t-;

            for(int k=i;k<j;k++)

            {

                dp_maxn[i][j]=max(dp_maxn[i][j],dp_maxn[i][k]+dp_maxn[k+][j]+sum[j]-sum[i-]);

                dp_minn[i][j]=min(dp_minn[i][j],dp_minn[i][k]+dp_minn[k+][j]+sum[j]-sum[i-]);

            }//cout<<i<<" "<<j<<" "<<dp_minn[i][j]<<endl;

        }

    int maxn=,minn=<<-;

    for(int i=;i<=n;i++) maxn=max(maxn,dp_maxn[i][i+n-]),minn=min(minn,dp_minn[i][i+n-]);

    cout<<minn<<endl<<maxn;

}

能量项链[loj 10148]

/*

为了好想 记录每一的head和tail

so dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+head[i]*tail[k]*tail[j])

i<=k<j

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

inline long long read()

{

    long long f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

long long dp[][],a[],h[],t[];

int main()

{

    long long n=read();

    for(long long i=;i<=n;i++) a[i]=read(),a[i+n]=a[i];

    for(long long i=;i<*n;i++) h[i]=a[i],t[i]=a[i+];

//    for(int i=1;i<2*n;i++) cout<<h[i]<<" "<<t[i]<<endl;

    for(long long tt=;tt<n;tt++)

        for(long long i=;i<=*n&&i+tt<=*n;i++)

        {

            long long j=i+tt;

//            cout<<i<<" "<<j<<endl;

            for(long long k=i;k<j;k++) dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+][j]+h[i]*t[k]*t[j]);

        }

    long long maxn=;

    for(long long i=;i<=n;i++) maxn=max(maxn,dp[i][i+n-]);

    cout<<maxn;

}

/*

7

23 17 212 113 71 301 33

31182687

*/

凸多边形的划分[loj 10149]

/*

高精度或__int128

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j])

dp[i][j][0]存位数

其他四个数一个int

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline long long read()

{

    long long f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return ans*f;

}

long long n,a[];

long long dp[][][];

long long s1[],s2[],s3[];

void print()

{

    cout<<dp[][n][dp[][n][]];

    for(long long i=dp[][n][]-;i>=;i--)

    {

        cout<<dp[][n][i]/;

        cout<<dp[][n][i]/%;

        cout<<dp[][n][i]/%;

        cout<<dp[][n][i]%;

    }

}

void mark(long long c[])

{

    for(long long i=;i<=c[];i++)

    {

        c[i+]+=c[i]/;

        c[i]%=;

    }

    while(c[c[]+]!=)

    {

        c[]++;

        c[c[]+]=c[c[]]/;

        c[c[]]%=;

    }

}

void mul(long long a1,long long a2,long long a3,long long c[])

{

    c[]=c[]=;

    for(long long i=;i<=c[];i++) c[i]*=a1;

    mark(c);

    for(long long i=;i<=c[];i++) c[i]*=a2;

    mark(c);

    for(long long i=;i<=c[];i++) c[i]*=a3;

    mark(c);

}

void add(long long a[],long long b[],long long c[])

{

    if(a[]>b[]) c[]=a[];

    else c[]=b[];

    for(long long i=;i<=c[];i++) c[i]=a[i]+b[i];

    mark(c);

}

long long compare(long long a[],long long b[])

{

    if(a[]>b[]) return ;

    if(a[]<b[]) return ;

    for(long long i=a[];i>=;i--)

    {

        if(a[i]<b[i]) return ;

        else if(a[i]>b[i]) return ;

    }

    return ;

}

int main()

{

    n=read();

    for(long long i=;i<=n;i++) a[i]=read();

    for(long long t=;t<=n-;t++)

    {

        for(long long i=;i+t<=n;i++)

        {

            long long j=i+t;

            dp[i][j][]=;

            for(long long k=i+;k<=j-;k++)

            {

                memset(s1,,sizeof(s1));

                memset(s2,,sizeof(s2));

                memset(s3,,sizeof(s3));

                mul(a[i],a[k],a[j],s1);

                add(dp[i][k],dp[k][j],s2);

                add(s1,s2,s3);

                if(compare(dp[i][j],s3))

                    memcpy(dp[i][j],s3,sizeof(s3));

            }

        }

    }

    print();

}

括号配对[loj 10150]

/*

dp[i][j]表示在[i,j]中至少需要添加的数量

1.  (i==[  j==] )  or(i==(   j==))  dp[i][j]=min(dp[i][j],dp[i+1][j-1]

2.  i==( or  i==[ dp[i][j]=min(dp[i][j],dp[i+1][j])

3.  j==) or j==]  dp[i][j]=min(dp[i][j],dp[i][j-1])

4. dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]) (i<=k<j)

初始化时dp[i][j]=inf  (i<=j) dp[i][i]=1;(1<=i<=n)

想一想为什么

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

char str[];

int a[];

int dp[][],inf=<<-;

int main()

{

//    memset(dp,127,sizeof(dp));

    scanf("%s",str+);

    int len=strlen(str+);

    for(int i=;i<=len;i++)

        for(int j=i;j<=len;j++) dp[i][j]=inf;

    for(int i=;i<=len;i++)

    {

        dp[i][i]=;

        if(str[i]=='(') a[i]=;

        if(str[i]==')') a[i]=;

        if(str[i]=='[') a[i]=;

        if(str[i]==']') a[i]=;

    }

    for(int t=;t<len;t++)

    {

        for(int i=;i+t<=len;i++)

        {

            int j=i+t;

            if((a[i]==&&a[j]==)||(a[i]==&&a[j]==)) dp[i][j]=min(dp[i][j],dp[i+][j-]);

            if(a[i]==||a[i]==) dp[i][j]=min(dp[i][j],dp[i+][j]+);

            if(a[j]==||a[j]==) dp[i][j]=min(dp[i][j],dp[i][j-]+);

            for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);

//            cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;

        }

    }

    cout<<dp[][len];

}

分离与合体[loj 10151]

/*

dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+(a[i]+a[j])*a[k])

i<=k<j

用last记录

bfs保证了一分为二，二分为四的输出

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

int n,a[],dp[][],last[][];

void bfs()

{

    queue< pair <int,int > > que;

    que.push(make_pair(,n));

    while(!que.empty())

    {

        pair<int,int> s=que.front();

        que.pop();

        if(s.first==s.second) continue;

        cout<<last[s.first][s.second]<<" ";

        que.push(make_pair(s.first,last[s.first][s.second]));

        que.push(make_pair(last[s.first][s.second]+,s.second));

    }

}

int main()

{

    n=read();

    for(int i=;i<=n;i++) a[i]=read();

    for(int t=;t<n;t++)

        for(int i=;i+t<=n;i++)

        {

            int j=i+t;

            for(int k=j-;k>=i;k--)

            {

                int t=dp[i][k]+dp[k+][j]+(a[i]+a[j])*a[k];

                if(t>=dp[i][j])

                {

                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+][j]+(a[i]+a[j])*a[k]);

                    last[i][j]=k;

                }

            }

        }

    cout<<dp[][n]<<endl;

    bfs();

    return ;

}

矩阵取数游戏[loj 10152]

/*

一行一行处理

dp[i][j]表示变到 i,j时的最大分数

dp[i][j]=max(dp[i][j],dp[i-1][j]*a[i-1]^pow(2,n+i-j-1),dp[i][j+1]*a[j+1]^pow(2,n+i-j-1))

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

inline long long read()

{

    long long f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

__int128 dp[][],ans,sry[];

long long n,m,a[];

void print(__int128 x)

{

    if(x==) return;

    else if(x!=) print(x/);

    putchar(x%+'');

}

int main()

{

    sry[]=;

    for(int i=;i<=;i++) sry[i]=sry[i-]*;

    n=read(),m=read();

    for(long long i=;i<=n;i++)

    {

        for(long long j=;j<=m;j++) a[j]=read();

        memset(dp,,sizeof(dp));

        for(long long i=;i<=m;i++)

            for(long long j=m;j>=i;j--)

                dp[i][j]=max(dp[i-][j]+a[i-]*sry[m-j+i-],dp[i][j+]+a[j+]*sry[m-j+i-]);

        __int128 maxn=-;

        for(long long i=;i<=m;i++) maxn=max(maxn,dp[i][i]+a[i]*sry[m]);

        ans+=maxn;

    }

    if(ans==)

    {

        cout<<;return ;}

    print(ans);

}
05-21 06:01
Powered by LMLPHP ©2024 LOJ 0.049759