欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

2020.7.27考试D1T2:方块消除(Block)

程序员文章站 2022-04-03 13:49:46
题目传送门DescriptionJimmy最近迷上了一款叫做方块消除的游戏. 游戏规则如下:n个带颜色方格排成一列,相同颜色的方块连成一个区域(如果两个相邻的方块颜色相同,则这两个方块属于同一个区域). 游戏时,你可以任选一个区域消去.设这个区域包含的方块数为x,则将得到x^2的分值.方块消去之后,右边的方格将向左移动.虽然游戏很简单,但是要得到高分也不是很容易.Jimmy希望你帮助他找出最高可以得到多少分.Input测试包括多个数据,数字给出一个数字T,表示有多少组数据。T<=15对于每...

注意!!!!传送门题目与本题解略有不符
区别在于题解为多组数据捆绑测试,传送门题目为单组数据测试
题目传送门

D1T2:方块消除(Block)

Description
Jimmy最近迷上了一款叫做方块消除的游戏. 游戏规则如下:n个带颜色方格排成一列,相同颜色的方块连成一个区域(如果两个相邻的方块颜色相同,则这两个方块属于同一个区域). 游戏时,你可以任选一个区域消去.设这个区域包含的方块数为x,则将得到x^2的分值.方块消去之后,右边的方格将向左移动.
虽然游戏很简单,但是要得到高分也不是很容易.Jimmy希望你帮助他找出最高可以得到多少分.
Input
测试包括多个数据,数字给出一个数字T,表示有多少组数据。T<=15对于每组数据,先给出一个数字N,1<=n<=200。表示有多少个方块,接下来一行N个数字表示每个方块的颜色,其值在1到N之间。
Output
对于每组数据,输出最大得分。格式如样例。
Sample Input
2
9
1 2 2 2 2 3 3 3 1
1
1
Sample Output
Case 1: 29
Case 2: 1

思路

这道题目表述的有一点不清晰~~(也可能是我理解能力太差了吧)~~
但大概就是:
T组数据,做T次
数据有n个数字,表示n个方块中,每个方块颜色
相邻的相同颜色的方块看做一组
不停删除任意一组相邻的相同颜色的方块
删除后,如果删除掉那组左右两边方块颜色相同便视为一组
删除时,每次删除区域长度平方的和

然后我们会想到用DP来解题
因为我们求删除区域长度平方的和,实质是求如何构成最长的区间长度

所以这是一道区间DP题目

而在考试时,因为种种原因 (不熟悉区间DP)
推导出的是有关树上的搜索题目
又没有剪枝和记忆化,所以超时

实际上,区间DP就是类似于向下划分,然后向上递推的某些树形结构

通常用划分区间的方法区间长度DP状态,一个区间的状态包含于该状态的更小区间得来

所以,本题也是这样的
消去一个区域,就会得到区域所含个数b[i]^2的值
并且消去该区域后,会使本来与被消去区域相邻的两个区域相邻

考试没有用DP还有一个重要的原因:
因为当前区域[l,r]的相邻的两个区域还可能在当前区域删去后合并
而如果只考虑区间[l,r]能得到的最大收益,一定是不全面

所以在考后研究发现需要再引入一维,作为dp[i][j][k]
表示:i到j的区域,右边有k个和a[i]接在后面最大收益

两种决策:

  1. 直接删除[i,j,k]这段区间,dp[i][j][k]=dp[i][j-1][0]+(a[j]+k)^2
  2. 在[i,j]区间中,寻找一个p连续方块,使得p与j是同一种类型的,那么可以,把p,j之间的方块删除后再进行删除,dp[i][j][k]=dp[i][p][len[j]+k]+dp[p+1][j-1][0]

然后对每个i,j遍历一遍所有的取法取最大值即可

注意在每组数据任务完成后初始化数组

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1010000];
int b[1010000];
int dp[100][100][100];
int s[1010000];
int main(){
	int t;
	cin>>t;
	for(int T=1;T<=t;T++){
		cin>>n;
	    for(int i=1;i<=n;i++){
	        cin>>a[i];
	    }
	    for(int i=1;i<=n;i++){
	        cin>>b[i];
	        s[i]=s[i-1]+b[i];
	    }
	    
	    //注意:这里的l指文中的i,r指j,k保持不变 
	    for(int i=0;i<=n;i++){
	        for(int l=1;l<=n;l++){
	            int r=l+i;
	            if(i+l>n){
	                break;
	            }
	            for(int k=0;k<=s[n]-s[r];k++){
	                dp[l][r][k]=dp[l][r-1][0]+(b[r]+k)*(b[r]+k);
	            }
	            for(int k=l;k<r;k++){
	                for(int j=0;j<=s[n]-s[r];j++){
	                    if(a[k]==a[r]){
	                        dp[l][r][j]=max(dp[l][r][j],dp[l][k][b[r]+j]+dp[k+1][r-1][0]);
	                    }
	                }
	            }
	        }
	    }
	    cout<<"Case "<<T<<" "<<dp[1][n][0]<<endl;
	    memset(dp,0,sizeof(dp));
	}
    return 0;
}

本文地址:https://blog.csdn.net/qq2718756941/article/details/107618113