清北学堂模拟赛day7 石子合并加强版

/*

注意到合并三堆需要枚举两个端点，其实可以开一个数组记录合并两堆的结果，标程好像用了一个神奇的优化

*/

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

#define ll long long

#define fo(i,l,r) for(int i = l;i <= r;i++)

#define fd(i,l,r) for(int i = r;i >= l;i--)

using namespace std;

const int maxn = ;

ll read(){

    ll x=,f=;

    char ch=getchar();

    while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};

    while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};

    return x*f;

}

int n;

ll dp[maxn][maxn],dp2[maxn][maxn],val[maxn],sum[maxn];

int main(){

    freopen("merge.in","r",stdin);

    freopen("merge.out","w",stdout);

    n = read();

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

    memset(dp2,/,sizeof(dp2));

    fo(i,,n) val[i] = read();

    fo(i,,n){

        dp[i][i] dp2[i][i] = ;

        sum[i] = sum[i-] + val[i];

    }

    for(int l = ;l <= n;l+=){

        for(int i = ;i + l - <= n;i++){

            int j = i + l - ;

            for(int k1 = i;k1 <= j;k1 += ){

                for(int k2 = k1 + ;k2 <= j;k2 += ){

                    dp[i][j] = min(dp[i][j],dp[i][k1] + dp[k1+][k2] + dp[k2+][j] + sum[j] - sum[i-]);

                }

            }

        }

    }

    cout<<dp[][n];

    return ;

} 

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef pair<int,int> pr;

const double pi=acos(-);

#define rep(i,a,n) for(int i=a;i<=n;i++)

#define per(i,n,a) for(int i=n;i>=a;i--)

#define Rep(i,u) for(int i=head[u];i;i=Next[i])

#define clr(a) memset(a,0,sizeof a)

#define pb push_back

#define mp make_pair

#define putk() putchar(' ')

ld eps=1e-;

ll pp=;

ll mo(ll a,ll pp){if(a>= && a<pp)return a;a%=pp;if(a<)a+=pp;return a;}

ll powmod(ll a,ll b,ll pp){ll ans=;for(;b;b>>=,a=mo(a*a,pp))if(b&)ans=mo(ans*a,pp);return ans;}

ll gcd(ll a,ll b){return (!b)?a:gcd(b,a%b);}

ll read(){

    ll ans=;

    char last=' ',ch=getchar();

    while(ch<'' || ch>'')last=ch,ch=getchar();

    while(ch>='' && ch<='')ans=ans*+ch-'',ch=getchar();

    if(last=='-')ans=-ans;

    return ans;

}

void put(ll a){

    if(a<)putchar('-'),a=-a;

    int top=,q[];

    while(a)q[++top]=a%,a/=;

    top=max(top,);

    while(top--)putchar(''+q[top+]);

}

//head

#define INF 1000000000

#define N 410

int n,f1[N][N],f2[N][N],a[N];

int main(){

    freopen("merge.in","r",stdin);

    freopen("merge.out","w",stdout);

    n=read();

    rep(i,,n)

        rep(j,,n)f1[i][j]=f2[i][j]=INF;

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

    rep(i,,n)f2[i][i]=;

    rep(i,,n-)f1[i][i+]=a[i+]-a[i-];

    rep(len,,n)

    rep(i,,n-len+){

        int j=i+len-;

        rep(k,i,j-)f2[i][j]=min(f2[i][j],f1[i][k]+f2[k+][j]+a[j]-a[k]);

        rep(k,i,j-)f1[i][j]=min(f1[i][j],f2[i][k]+f2[k+][j]+a[j]-a[i-]);

    }

    cout<<f2[][n]<<endl;

    return ;

}
秒客网

清北学堂模拟赛day7 石子合并加强版

相关文章
