南昌网站建设利润,资源网站自己建设还是发软文,wordpress 51,什么是网站源码题目描述
n个木块排成一列#xff0c;每个木块都有一个颜色。
每次#xff0c;你都可以点击一个木块#xff0c;这样被点击的木块以及和它相邻并且同色的木块就会消除。 如果一次性消除了k个木块#xff0c;那么就会得到k*k分。
给定你一个游戏初始状态#xff0c;请你…题目描述
n个木块排成一列每个木块都有一个颜色。
每次你都可以点击一个木块这样被点击的木块以及和它相邻并且同色的木块就会消除。 如果一次性消除了k个木块那么就会得到k*k分。
给定你一个游戏初始状态请你求出最高得分是多少。
解析
区间dp 首先可以把同色合并从而将数列转化为一个由若干段组成的新的数列 用dp[i][j][k]表示新数列中在加上后面有k个与第j段颜色相同的木块的情况下第i到j段的最大得分 那么就可以不断把第r段尝试与之前的同色段连接消除并继续递归
for(int il;ir;i){if(co[i]co[r]){dp[l][r][k]max(dp[l][r][k],solve(l,i,len[r]k)solve(i1,r-1,0));}}从而完成本题
代码
#include cstdio
#include cstring
#include cmath
#include algorithm
#include iostream
#include string
#include queue
#include string
#includemap
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a));
#define ull unsigned ll
using namespace std;
const int N250;
int m,n,ans;
int dp[N][N][N],a[N];
int len[N],co[N],tot;
int solve(int l,int r,int k){if(lr) return 0;if(dp[l][r][k]) return dp[l][r][k];if(lr) return dp[l][r][k](len[l]k)*(len[l]k);dp[l][r][k]solve(l,r-1,0)(len[r]k)*(len[r]k);for(int il;ir;i){if(co[i]co[r]){dp[l][r][k]max(dp[l][r][k],solve(l,i,len[r]k)solve(i1,r-1,0));}}return dp[l][r][k];
}
int main(){scanf(%d,m);for(int p1;pm;p){scanf(%d,n);mem(dp,0);mem(len,0);mem(co,0);tot0;for(int i1;in;i){scanf(%d,a[i]);if(i1||a[i]!a[i-1]){co[tot]a[i];len[tot]1;}else len[tot];}printf(Case %d: %d\n,p,solve(1,tot,0));}
}
心得
本题参考了题解。。。 主要就是这个dp的定义和向前递归的思想没有想到 本来一直在枚举长度找递推式awa 而其实递推能做的dp递归应该也可以时间复杂度不会差太多也就亿点点 所以
dp要优先考虑递归
thanks for reading
