Demo entry 6709392

te

   

Submitted by anonymous on Feb 02, 2018 at 04:26
Language: C++. Code size: 1.1 kB.

#include<bits/stdc++.h>  
using namespace std;  
#define inf 9999999  
int n,a[300],sums[210];  
int dp[210][210];//dp[i][j]表示把i开头j结尾的石子合并所需最大得分  
int dpmin[210][210];  
int main()  
{  
    scanf("%d",&n);  
    for(int i=1;i<=n;i++)  
    {  
        scanf("%d",&a[i]);  
        a[i+n]=a[i];  
        a[i+2*n]=a[i];  
    }  
    for(int i=1;i<=2*n;i++)  
    {  
        sums[i]+=sums[i-1]+a[i];  
    }  
    for(int i=2*n-1;i>=1;i--)  
    {  
        for(int j=i+1;j<=n+i-1;j++)  
        {  
            dpmin[i][j]=inf;  
            for(int k=i;k<j;k++)  
            {  
                dpmin[i][j]=min(dpmin[i][j],dpmin[i][k]+dpmin[k+1][j]+sums[j]-sums[i-1]);  
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sums[j]-sums[i-1]);  
            }  
        }  
    }  
            int maxnum=0,minnum=inf;  
            for(int i=1;i<=n;i++)  
            {  
                minnum=min(minnum,dpmin[i][i+n-1]);  
                maxnum=max(maxnum,dp[i][i+n-1]);  
            }  
    printf("%d\n%d",minnum,maxnum);  
}  

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).