合并石子

这个就强调一点:一定要分清是线性排列还是环形排列,如果是环形的话,只需要将n+1--2n重新赋一遍值,

但是:!!!s[i]要继续s[i]=s[i-1]+a[i],而且别忘了给f[n+1][n+1]---f[2n][2n]赋一遍0

我也在这个上错了好几次!

线性实现:

#include<iostream>
#include<cstring>
int f[1000][1000],s[10000];
int k,n;
using  namespace std;
int main()
{
    cin>>n;
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        cin>>k;
        s[i]=s[i-1]+k;
        f[i][i]=0;
    }
    
    
    for(int len=2;len<=n;len++)
    {
        for(int l=1;len+l-1<=n;l++)
        {
            int r=l+len-1;
            for(int k=l;k<r;k++)
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    }
    cout<<f[1][n];
    return 0;
}

环形实现:

#include<iostream>
#include<cstring>
int f[1000][1000],s[10000],a[10000];
int k,n,maxn,miny=100000000;
using  namespace std;
int main()
{
    cin>>n;
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
        f[i][i]=0;        

    }
    for(int i=n+1;i<2*n;i++)
    {
        a[i]=a[i-n];
        s[i]=s[i-1]+a[i];
        f[i][i]=0;        
    }
//    len+l-1=j
    //j-l=len-1
    for(int len=2;len<=n;len++)
    {
        for(int l=1;len+l-1<=2*n;l++)
        {
            int r=l+len-1;
            for(int k=l;k<r;k++)
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    }
    miny=f[1][n];
    for(int i=2;i<=n;i++)
    {    
        miny=min(miny,f[i][i+n-1]);
    }
//    cout<<f[1][n]<<endl;
    cout<<miny<<endl;
    memset(f,0,sizeof(f));
    for(int len=2;len<=2*n;len++)
    {
        for(int l=1;len+l-1<=2*n;l++)
        {
            int r=l+len-1;
            for(int k=l;k<r;k++)
                f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    }
//    cout<<f[1][n];
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,f[i][i+n-1]);
    }
    cout<<maxn;
    return 0;
    } 

我这个程序揉合了两部分,我相信优秀的audience(读者)一定可以看得明白

(yes