洛谷 P1880 石子合并

 

题目描述

在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

输入输出格式

输入格式:

 

数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

 

输出格式:

 

输出共2行,第1行为最小得分,第2行为最大得分.

 

输入输出样例

输入样例#1:
4
4 5 9 4
输出样例#1:
43
54

解题思路

  由于是环形的,所以我们把石子复制一遍,比如5堆石子,从第4堆环形合并到第3堆(4、5、1、2、3),复制后石子编号就是4 5 6 7 8了,复制一遍就能拆环,直接当做两倍长的链处理。

  在这条链上,用动规数组f[j][i](代码风格太迷,一不小心反了)表示第i堆到第j堆所得积分的极值,它等于i到j的石子总数加已得积分的极值。比如要求2~5的积分,我们可以通过这么几种方式合并出2~5—— 2+3~5 2~3+4~5 2~4+5。求出这几种方式哪种能得到最多或最少的积分,一路求下去直到全部合成一堆为止。

源代码

#include<stdio.h>
#include<string.h>
int a[210]={0};
int f[210][210]={0};
int s[210]={0};
int n,ans;
inline int max(int a,int b)
{
    return a>b?a:b;
}
inline int min(int a,int b)
{
    return a<b?a:b;
}
void print()
{
    for(int i=1;i<=n<<1;i++)
    {
        for(int j=1;j<=n<<1;j++)
            printf("%4d",f[i][j]);
        printf("\n");
    }
    printf("\n");
}
int main()
{
    //freopen("test.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i),s[i]=s[i-1]+a[i];
    for(int i=n+1;i<=n<<1;i++)
        s[i]=s[i-1]+a[i-n];

    memset(f,0,sizeof(f));
    for(int i=2;i<=n;i++)
    {
        int c=i-1;
        for(int j=1;j<=(n<<1)-c;j++)
        {
            int minn=999999999;
            f[j+c][j]=s[j+c]-s[j-1];
            if(c==1) minn=0;
            for(int k=0;k<c;k++)
                minn=min(minn,f[j+k][j]+f[j+c][k+j+1]);
            f[j+c][j]+=minn;
        }//print();
    }
    ans=999999999;
    for(int i=n;i<=n<<1;i++)
        ans=min(ans,f[i][i-n+1]);
    printf("%d\n",ans);
    
    memset(f,0,sizeof(f));
    for(int i=2;i<=n;i++)
    {
        int c=i-1;
        for(int j=1;j<=(n<<1)-c;j++)
        {
            int maxn=-1;
            f[j+c][j]=s[j+c]-s[j-1];
            if(c==1) maxn=0;
            for(int k=0;k<c;k++)
                maxn=max(maxn,f[j+k][j]+f[j+c][k+j+1]);
            f[j+c][j]+=maxn;
        }//print();
    }
    
    ans=-1;
    for(int i=n;i<=n<<1;i++)
        ans=max(ans,f[i][i-n+1]);
    printf("%d",ans);

    
    return 0;
}

 Ps:

  这题半年前就想写了,但由于码力不足,一直没动,今晚总算把它a了。

  现在时间:2017年06月03日02:26:43。凌晨做题真有意思,总是想睡觉又想切了这题再睡。

  由于状态转移掌握不太熟,一个状态从哪些情况转移过来(代码里的第三重循环),脑子不清楚,于是那段我是"调参"调出来的,我这种写法细节要注意的太多了……网上其他题解的状态转移写的真心简洁,循环方式也不同,代码量就少了很多,以后还要多多学习呀

上一篇:洛谷 P1330 *阳光大学


下一篇:洛谷 P2587 BZOJ 1034 [ZJOI2008]泡泡堂