首页 > 其他 > 详细

P1880 NOIP 1995石子合并

时间:2019-06-19 21:52:24      阅读:79      评论:0      收藏:0      [点我收藏+]

复习(du) 这道题,发现思想真不错

当时背板子打下来的

要下晚自习了,明天更注释吧

#include<iostream>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int f2[200][200],f1[200][200];
int s[1008],n;
int a[1008];
int ans1,ans2;
int sum(int left,int right)
{
    return s[right]-s[left-1];
}
int main()
{
    memset(f1,-1,sizeof(f1));
    memset(f2,0x3f,sizeof(f2));
    int i,j;
    scanf("%d ",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=a[i]+s[i-1];
        a[i+n]=a[i];
        f1[i][i]=0;
        f2[i][i]=0;
    }
    for(i=n+1;i<=n*2;i++)
    {
    s[i]=a[i]+s[i-1];
    f1[i][i]=0;
    f2[i][i]=0;    
    }
    
    int l,k;
    for(l=2;l<=n;l++)
    for(i=1;i<=2*n-l;i++)
    {
        j=i+l-1;
        for(k=i;k<j;k++)
        {
            f1[i][j]=max(f1[i][k]+f1[k+1][j],f1[i][j]);
            f2[i][j]=min(f2[i][k]+f2[k+1][j],f2[i][j]);
        }
        f1[i][j]+=sum(i,j);
        f2[i][j]+=sum(i,j); 
    }
    ans1=-1;
    ans2=0x3f3f3f3f;
    for(i=1;i<=n;i++)
    {
        ans1=max(ans1,f1[i][i+n-1]);
        ans2=min(ans2,f2[i][i+n-1]);
     } 
     printf("%d\n%d ",ans2,ans1);
     return 0;
}

 

P1880 NOIP 1995石子合并

原文:https://www.cnblogs.com/zsx6/p/11054832.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!