0x53 区间DP

石子合并搞笑

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int s[];

int f[][];

int main()

{

    int n,x;

    scanf("%d",&n);

    s[]=;

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

        scanf("%d",&x), s[i]=s[i-]+x, f[i][i]=;

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

    {

        for(int l=;l+L-<=n;l++)

        {

            int r=l+L-; f[l][r]=;

            for(int i=l;i<r;i++)

            {

                f[l][r]=min(f[l][r],f[l][i]+f[i+][r]+s[r]-s[l-]);

            }

        }

    }

    printf("%d\n",f[][n]);

    return ;

}

石子合并

poj1179 神经。。出答案的时候n写成n-1wa了两次

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int a[]; char c[],sc[];

int mx[][],mn[][];

int aslen,as[];

int main()

{

    int n,x;

    while(scanf("%d",&n)!=EOF)

    {

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

        {

            scanf("%s%d",sc+,&a[i]);

            c[i-]=sc[];

            mx[i][i]=mn[i][i]=a[i];

            if(i!=n)

            {

                c[i-+n]=c[i-];

                a[i+n]=a[i];

                mx[i+n][i+n]=mn[i+n][i+n]=a[i];

            }

        }

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

        {

            for(int l=;l+L-<=*n-;l++)

            {

                int r=l+L-;

                mx[l][r]=-;

                mn[l][r]=;

                for(int i=l;i<r;i++)

                {

                    if(c[i]=='t')

                    {

                        mx[l][r]=max(mx[l][r],mx[l][i]+mx[i+][r]);

                        mn[l][r]=min(mn[l][r],mn[l][i]+mn[i+][r]);

                    }

                    else

                    {

                        mx[l][r]=max(mx[l][r],max(mx[l][i]*mx[i+][r],mn[l][i]*mn[i+][r]));

                        mn[l][r]=min(mn[l][r],min(mx[l][i]*mx[i+][r],mn[l][i]*mn[i+][r]));

                    }

                }

            }

        }

        int mmax=mx[][n];

        aslen=, as[++aslen]=;

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

            if(mx[i][i+n-]>mmax)

            {

                mmax=mx[i][i+n-];

                aslen=, as[++aslen]=i;

            }

            else if(mx[i][i+n-]==mmax) as[++aslen]=i;

        printf("%d\n",mmax);

        for(int i=;i<=aslen;i++)printf("%d ",as[i]);

        printf("\n");

    }

    return ;

}

poj1179

金字塔怎么这里的题要么简单得要死要么难得要死啊这个搜索顺序就。。和树上差分没撒区别嘛，我的想法是区间视作子树合并就乘起来

虽然想法好像很对而我还是太naive了不会写

对于一个区间[l,r]假如ss[l]==ss[r]，那么我们可以把l+1~r-1视作一棵子树

对于当前询问的区间，枚举断点i，l+1~i形成一棵子树，让i+1~r去继续分割，同时，这样可以保证没有重复，因为1~i每次的大小不一样

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const int mod=1e9;

char ss[];

int f[][];

int dfs(int l,int r)

{

    if(l>r||ss[l]!=ss[r])return ;

    if(l==r)return ;

    if(f[l][r]!=-)return f[l][r];

    f[l][r]=;

    for(int i=l+;i<r;i++)

        f[l][r]=( ((LL)f[l][r]) + ((LL)dfs(l+,i)) * ((LL)dfs(i+,r)) )%mod;

    return f[l][r];

}

int main()

{

    scanf("%s",ss+);

    memset(f,-,sizeof(f));

    printf("%d\n",dfs(,strlen(ss+)));

    return ;

}

金字塔

巴特西

0x53 区间DP

最新文章

热门文章