解题报告 P2858 [USACO06FEB]Treats for the Cows G/S

题目内容

P2858

大意:n 个元素的序列,每次可以从头或者尾去掉一个元素,获得的收益是这个元素的权值乘上该次去除的次数,求最大收益。

解题思路

不难发现,这题由于去除元素的顺序对最终的结果是有影响的,所以不能直接贪心,考虑使用 dp。

这题一眼看上去像是一个区间 dp,那我们先开始寻找如何定义状态。考虑我们已经去除了 [i,j] 以外的所有元素,可以发现外面元素去除的顺序已经不重要了,满足无后效性,说明可以这样定义状态:f_{i,j} 表示还剩 [i,j] 时可以达到的最大收益。

转移:当我们达到 [i,j] 时,要么是去掉了第 i-1 个元素,要么是去掉了第 j+1 个元素,设当前的天数为 d,第 i 个元素为 v_i,则有状态转移方程

f_{i,j}=\max(f_{i-1,j}+dv_{i-1},f_{i,j+1}+dv_{j+1})

那么枚举区间长度的时候就必须从大到小枚举,为了方便可以在枚举区间长度的同时枚举天数

最后统计答案的时候答案为 ans=\displaystyle\max_{i=1}^n\lbrace f_{i,i}+nv_i\rbrace,输出即可。

#include <cstdio>
#include <cctype>

//快读

//max

const int maxn=2005;
int v[maxn],f[maxn][maxn];

int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
        v[i]=read();
    for(int len=n-1,day=1;len>=1;len--,day++)//从n-1开始枚举区间长度
        for(int i=1,j=i+len-1;j<=n;i++,j++)
            f[i][j]=max(f[i][j+1]+v[j+1]*day,f[i-1][j]+v[i-1]*day);
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i][i]+n*v[i]);
    printf("%d\n",ans);
    return 0;
}

当然,这题正序枚举区间长度也是可以的,只是倒序的更好理解我太菜不会

解题报告 CF607B Zuma

题目内容

CF607B

大意:给定一串序列,每次操作可以消除其中的一个回文串并将两侧拼一起,求消除所有元素所需的最小操作次数

解题思路

区间 dp

f_{i,j} 表示区间 [i,j] 需要的最小消除次数,接下来考虑转移:

显然,有

\begin{cases}
f_{i,i}=1\quad\
f_{i,i+1}=1\quad(a_i=a_j)\
f_{i,i+1}=2\quad(a_i\neq a_j)
\end{cases}

可发现的就是,如果串的长度为 1,则需要的消除次数为 1,如果长度为 2,则次数取决于这两个元素是否相等,相等就只需要一次,不相等就需要两次。

然后,一般地,如果当前枚举的两端点元素相等,说明可以在消除中间的元素的同时顺便消掉两边元素,但如果不相等,就只能枚举断点寻找最优划分方案,即:

\begin{cases}
f_{i,j}=f_{i+1,j-1}\qquad\qquad\qquad(a_i=a_j)\
f_{i,j}=\min_{k=i}^{j-1}\lbrace f_{i,k}+f_{k+1,j}\rbrace~(a_i\neq a_j)
\end{cases}

需要注意的是,不一定两端点元素相等了f_{i+1,j-1} 就是最优解,仍然需要考虑取断点的情况,否则会 WA,hack 数据:

10
1 2 3 5 3 2 1 1 3 1

上面的就是一个典型的不可通过直接取 f_{i+1,j-1} 得到答案的例子,如果在最后一步的时候直接套用 f_{2,9},得到的答案是 3,但是正确的结果是 2,由 f_{1,7}+f_{8,10} 得来

剩下的就很简单了,只需记得一开始 f 数组初始化为 inf 即可。

#include <cstdio>
#include <cctype>
#include <cstring>

const int maxn=505;
int n,a[maxn],f[maxn][maxn];

//快读已省略

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    n=read();
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
        a[i]=read(),f[i][i]=1;
    for(int i=1;i<n;i++)
        f[i][i+1] = 1+(a[i]!=a[i+1]);//处理长度为2的情况
    for(int l=3;l<=n;l++)
        for(int i=1,j=i+l-1;j<=n;i++,j++)
        {
            if(a[i]==a[j])
                f[i][j]=f[i+1][j-1];
            for(int k=i;k<j;k++)
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
        }
    printf("%d\n",f[1][n]);
    return 0;
}

解题报告 P4170 [CQOI2007]涂色

题目内容

P4170

大意:给出一块木板,要求涂色,后覆盖前,求最小笔刷数

解题思路

区间 dp。

不难发现,定义状态 f_{i,j}[i,j] 的最少次数可以满足最优子结构和无后效性,具体就是要看如何转移。

枚举端点 ij,发现如果有 s_i=s_j 的话,相当于第一次涂色的时候多涂一格,转移方程为 f_{i,j}=\min(f_{i,j-1},f_{i+1,j})

但如果 s_i\neq s_j 的话,说明没办法直接多涂一格,需要枚举中间的断点 k,由于枚举 k 的过程中必然能找到一种划分方式使得总的涂色次数加起来最优,因此只需要将断点左右加起来取最小值就可以得到该区间的答案,故有如下方程:

f_{i,j}=\min_{k\in[i,j)} \lbrace f_{i,k}+f_{k+1,j}\rbrace

#include <cstdio>
#include <cstring>

int f[55][55];

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    int n;
    char s[55];
    scanf("%s",s+1);
    n=strlen(s+1);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
        f[i][i]=1;
    for(int l=1;l<n;l++)
        for(int i=1,j=l+1;j<=n;i++,j++)
            if(s[i]==s[j])
                f[i][j]=min(f[i][j-1],f[i+1][j]);
            else
                for(int k=i;k<j;k++)
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
    printf("%d\n",f[1][n]);
    return 0;
}

解题报告 P1063 能量项链【NOIP2006TGT1】

题目内容

P1063

本题对于题意的理解很重要

Mars 星球上,每个 Mars 人都随身佩带着一串能量项链。在项链上有 N 颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是 Mars 人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 m,尾标记为 r,后一颗能量珠的头标记为 r,尾标记为 n,则聚合后释放的能量为 m \times r \times nMars 单位),新产生的珠子的头标记为 m,尾标记为 n

需要时,Mars 人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。

例如:设 N=44 颗珠子的头标记与尾标记依次为 (2,3) (3,5) (5,10) (10,2)。我们用记号 表示两颗珠子的聚合操作,(j⊕k) 表示第 j,k 两颗珠子聚合后所释放的能量。则第 4、1 两颗珠子聚合后释放的能量为:

(4⊕1)=10 \times 2 \times 3=60=10×2×3=60

第一行是一个正整数 N(4≤N≤100),表示项链上珠子的个数。第二行是 N 个用空格隔开的正整数,所有的数均不超过 1000。第 i 个数为第 i 颗珠子的头标记 (1≤i≤N),当 i 时,第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记。第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。

至于珠子的顺序,你可以这样确定:将项链放到桌面上,不要出现交叉,随意指定第一颗珠子,然后按顺时针方向确定其他珠子的顺序。

解题思路

一个项链,说明是环形区间 dp,但这题比较注重细节。我们设 f(i,j) 表示区间 [i,j] 上的所有珍珠合并后能释放的最大能量,而 a_i 又是第 i 颗珠子的头标记,所以我们有如下的状态转移方程:

f(i,j)=\max_{k\in [i,j)}\lbrace f(i,k)+f(k+1,j)+a_i\times a_{k+1}\times a_{j+1}\rbrace

这个方程的解释:首先枚举 k 作为断点,表示将区间 [i,k](k,j] 的珠子合并,而合并释放的能量是前珠子的头标记乘 k 珠子的尾标记乘后珠子的尾标记,必须清楚自己设的东西表示的是什么否则就是像我一样调半个小时

除此之外没有什么难点,代码见下:

#include <cstdio>
inline int max(int a,int b)
{
    return a>b?a:b;
}

const int maxn=205;
int n,f[maxn][maxn],a[maxn];

//f[i][j]表示[i,j]区间内的珠合并后能达到的最大价值

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        a[n+i]=a[i];//常规环状展开
    }
    int ans=0;
    for(int l=2;l<=n;l++)//l表示枚举的区间长度
        for(int i=1,j=i+l-1;i<n<<1&&j<=n<<1;i++,j++)//枚举左右端点
            for(int k=i;k<j;k++)//然后枚举中间断点
            {
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);//转移方程
                ans=max(ans,f[i][j]);//其实可以直接统计答案
            }
    printf("%d\n",ans);
    return 0;
}

解题报告 P1880 [NOI1995]石子合并

题目内容

P1880

大意:n 堆石子摆一圈,每次选相邻的两堆合在一起,并将新的一堆的石子数,记为该次合并的得分。求合并成 1 堆后的最大和最小得分。

解题思路

区间 dp 模板题

像这类满足可以区间合并最优的 dp,一般都是进行分段分段的求阶段性最优值,再依次合并。这类问题一般都是枚举一个区间长度 l,然后依次枚举左右端点,再枚举中间的断点 k,进行子问题的合并。比如这题,令 f(i,j) 表示在区间 [l,r] 上进行合并能达到的最大得分,转移方程就是

f(i,j)=\max_{k\in[l,r)}\lbrace f(i,j),f(i,k)+f(k+1,r)+sum(i,j)\rbrace

其中 sum(i,j) 表示这一段的石子数量的区间和,可以前缀和预处理达到

然后由于这个题中是一个环,所以考虑把这个环延长成两倍,然后不要忘记所有流程都扩成两倍,然后最后统计答案的时候遍历一遍即可。时间复杂度 O(n^3) (一层枚举区间长度,一层枚举区间左右端点,一层枚举中间断点 k

#include <cstdio>

const int maxn=105;
int a[maxn<<1],f1[maxn<<1][maxn<<1],f2[maxn<<1][maxn<<1],n,s[maxn<<1];
//a为每一堆的数量,f1为最大值,f2为最小值,s为石子堆数的前缀和

inline int max(int a,int b)//不想用algorithm库的
{
    return a>b?a:b;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        a[n+i]=a[i];//记得copy一份
    }
    for(int i=1;i<=n<<1;i++)
        s[i]=s[i-1]+a[i];//前缀和处理
    for(int l=1;l<n;l++)//枚举区间的长度,这里的l其实是实际长度-1
        for(int i=1,j=i+l;j<n<<1&&i<n<<1;i++,j=i+l)//枚举i,j,注意i和j之间的宽度是固定的
        {
            f2[i][j]=0x3f3f3f3f;//先给他一个无穷大
            int d=s[j]-s[i-1];//后面要用到的就先处理了
            for(int k=i;k<j;k++)//枚举中间断点k
            {
                f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+d);
                f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+d);
            }
        }
    int ans1=0,ans2=0x3f3f3f3f;
    for(int 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\n",ans2,ans1);//注意先最小后最大
    return 0;
}