AcWing 322. 消木块 区间dp+分治
标签：win == namespace cas 间接 main iostream 往里面 调用
#include
#include
#include
#include
using namespace std;
const int N=210;
int t,n;
int col[N],A[N],len[N],dp[N][N][N];
//dp[i][j][k]代表消除第 i~j 块且区间最右边留下了 k 个与 j 颜色相同的方块的最大价值
int solv(int l,int r,int last) {
//如果左右端点相同了，那么就直接消除
if(l==r)
return (len[r]+last)*(len[r]+last);
//如果之前搜过了，直接调用
if(dp[l][r][last])
return dp[l][r][last];//记忆化
//将 r~last 合并并消除,因为后面被消除,所以不存在与 r-1 颜色相同的
//不存在与r-1颜色相同是因为，从原始数组的左右区间开始往里面递归的
//再看下面的递推式子，会发现，r~las合并之后，后面就不会存在与r-1颜色相同的
dp[l][r][last]=solv(l,r-1,0)+(len[r]+last)*(len[r]+last);
for(int i=l; i+1
AcWing 322. 消木块 区间dp+分治
标签：win == namespace cas 间接 main iostream 往里面 调用
原文地址：https://www.cnblogs.com/QingyuYYYYY/p/12604557.html
评论