T1 Cow BFS

众所周知,搜索是万能的。

大致题意:

给定一个$N*M$的矩阵,从$(1,1)$走到$(N,M)$,每一步可以向右上,右, 或是右下方向。路径上经过的点$(i,j)$都附带一个权值$a_{i,j}$,求最大路径权值和。

其中$N,M≤100$。所以只需要一个搜索就可以完成了。

但是需要注意的是,随手打的记忆化如果不加,貌似会TLE。

所以记录一个$ans_{i,j}$表示走到点$(i,j)$的时候的最大路径权值和。初始极大值。

完了。就一BFS板子题。

$CODE$

#include<bits/stdc++.h>
#define ok(x,y) (x>=1&&x<=n&&y>=1&&y<=m)
using namespace std;
int a[110][110];
int ans[110][110];
int dir[3][2]={0,1,1,1,-1,1};
struct node{int x,y,w;};
int n,m;
int bfs()
{
    queue<node> q;
    q.push((node){1,1,a[1][1]});
    while(!q.empty())
    {
        int x=q.front().x,y=q.front().y,w=q.front().w;
        q.pop();
        if(x==n&&y==m)
            return w;
        for(int i=0;i<3;i++)
        {
            int dx=x+dir[i][0],dy=y+dir[i][1];
            if(ok(dx,dy)&&w+a[dx][dy]>ans[dx][dy])
                ans[dx][dy]=w+a[dx][dy],q.push((node){dx,dy,w+a[dx][dy]});
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    bfs();
    printf("%d\n",ans[n][m]);
    return 0;
}

T2 Block DP

呕呕呕呕呕呕呕呕呕

可以,这道题够恶心。

大致题意:

有$n$个带有颜色的方块,每消除一段长度为$x$的连续的相同颜色的方块可以得到的$x^2$分数并把剩余两边拼在一起,让你用一种最优的顺序消除所有方块使得得分最多。

其中$1≤n\leq 200$。

首先能够想到的是用$f[i][j]$表示消掉区间$[i,j]$之后的最大得分。但是。。

打一打就会发现,这个状态还会受区间外的元素影响,比如1111222111,先消1111不能取得最优(贪心错误同理)。

那就再加一维!接下来的是真的挺妙的一个状态表示

用$f[i][j][k]$表示消掉了区间$[i,j]$,并且在$j$之后还有连续$k$个和第$j$个盒子颜色相同。

注意这里的连续,是指消掉了一些盒子之后连续,而不是输入的连续色块

然后就来状态转移吧!

首先,我们可以同时消掉$j$和$j$后面的$k$个盒子。此时$f[i][j][k]=max(f[i][j][k],f[i][j-1][0]+(k+1)^2)$

然后,假设在区间$[i,j]$中有一个和$j$颜色相同的盒子$p$,所以我们就把$[p+1,j-1]$这一段消掉,然后让$p$和后面$k+1$个相同颜色的拼在一起。此时$f[i][j][k]=max(f[i][j][k],f[i][p][k+1]+f[p+1][j-1][0])$

怎么枚举$k$呢?我们可以记录一个$sum[i][j]$表示在$[1,j]$中有多少个$i$。因为是前缀和所以减就完了。

注意外层枚举$i$的时候要逆循环,因为第三维是$j$右边的同颜色个数,而$j$又是从$i$开始的,所以我们$i$如果逆循环的话就可以轻松枚举第三维了。

$CODE$

#include<bits/stdc++.h>
using namespace std;
int n,t;
const int N=210;
int a[N],sum[N][N],f[N][N][N];
int main()
{
    scanf("%d",&t);
    for(int kk=1;kk<=t;kk++)
    {
        memset(sum,0,sizeof(sum));
        memset(f,0,sizeof(f));
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            for(int j=1;j<=200;j++)
                sum[j][i]=sum[j][i-1];
            sum[a[i]][i]++;
        }
        
        for(int i=n;i>=1;i--)
            for(int j=i;j<=n;j++)
            {
                for(int p=i;p<j;++p)
                    if(a[p]==a[j])
                        for(int k=0;k<=sum[a[j]][n]-sum[a[j]][j];k++)
                            f[i][j][k]=max(f[i][j][k],f[i][p][k+1]+f[p+1][j-1][0]);
                for(int k=0;k<=sum[a[j]][n]-sum[a[j]][j];k++)
                    f[i][j][k]=max(f[i][j][k],f[i][j-1][0]+(k+1)*(k+1));
            }        
        printf("Case %d: %d\n",kk,f[1][n][0]);    
    }        
    return 0;
}
//代码不要问 问就是抄的
最后修改:2020 年 07 月 27 日 07 : 19 PM