20180614 DP4训练 K - Blocks（区间DP）

本文主要是介绍20180614 DP4训练 K - Blocks（区间DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

有一串长度为n的块，每次可以消去x个连续的相同的块，并且获得的值为x*x，问消去所有快能获得的最大价值？

思路：

区间DP。一开始没搞明白这个题目什么意思，理解错了，其实把区间分割完之后在合并，不是最优的，因此不能单独考虑每个区间。在每个区间（x，y）里面，在i的位置，我们只需要统计他的前面有多少相同的块，dp[i][j][k]其中k表示i前面的相同得块的个数，dp【i】【j】【k】整体即表示消去前面k个颜色相同的块和区间【i，j】里的块可以获得的最大价值。状态转移方程为：

dp[i][j][k] = max(dp[i+1][j][k] + (1 + k) * (1 + k), dp[l][j][k+1] + dp[i+1][l-1][0]);

代码:

#include <bits/stdc++.h>
using namespace std;
#define M 250
#define INF ox3f3f3f3f
int a[M];
int dp[M][M][M];
int dfs(int i,int j,int k)  //DFS区间
{if(dp[i][j][k]!=-1)return dp[i][j][k];  //记忆化保存if(i>j){                 //i>j不符合条件dp[i][j][k]=0;return 0;}dp[i][j][k]=dfs(i+1,j,0)+(1+k)*(1+k);for(int l=i+1;l<=j;l++){if(a[l]==a[i])dp[i][j][k]=max(dp[i][j][k],dfs(l,j,k+1)+dfs(i+1,l-1,0));  //关键状态方程}return dp[i][j][k];
}
int main()
{int T,cas=1;scanf("%d",&T);while(T--){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}memset(dp,-1,sizeof(dp));printf("Case %d: %d\n",cas++,dfs(1,n,0));}return 0;
}

这篇关于20180614 DP4训练 K - Blocks（区间DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---