关键词：
| Time Limit: 5000MS | Memory Limit: 65536K | |
| Total Submissions: 4318 | Accepted: 1745 |
Description
The corresponding picture will be as shown below:
Figure 1
If some adjacent boxes are all of the same color, and both the box to its left(if it exists) and its right(if it exists) are of some other color, we call it a ‘box segment‘. There are 4 box segments. That is: gold, silver, bronze, gold. There are 1, 4, 3, 1 box(es) in the segments respectively.
Every time, you can click a box, then the whole segment containing that box DISAPPEARS. If that segment is composed of k boxes, you will get k*k points. for example, if you click on a silver box, the silver segment disappears, you got 4*4=16 points.
Now let‘s look at the picture below:
Figure 2
The first one is OPTIMAL.
Find the highest score you can get, given an initial state of this game.
Input
Output
Sample Input
2 9 1 2 2 2 2 3 3 3 1 1 1
Sample Output
Case 1: 29 Case 2: 1
递归形式的动态规划：dp[st][ed][len]从st到ed全然消除。且ed右边挨着有一个len的大块颜色和ed同样.
一种消除方式是，Len块直接和ed块合并直接消除得到分数work（st,ed-1,0）+（a[ed].n+len）*(a[ed].n+len);
还有一种是在st到ed之间找到一个块p和ed块颜色同样，把这3块直接合并 work（st,p，a[ed].n+len）+work(p+1,ed-1,0);
两种方式取最大的值。
当st==ed时递归结束。
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
using namespace std;
#define LL __int64
#define N 210
const int inf=0x1f1f1f1f;
struct node
{
int c,n,p;
}a[N];
int f[N][N][N];
int work(int st,int ed,int len)
{
if(f[st][ed][len])
return f[st][ed][len];
int i,ans=(a[ed].n+len)*(a[ed].n+len);
if(st==ed)
{
f[st][ed][len]=ans;
return ans;
}
ans+=work(st,ed-1,0);
for(i=ed-1;i>=st;i--)
{
if(a[i].c!=a[ed].c)
continue;
int tmp=work(st,i,a[ed].n+len)+work(i+1,ed-1,0);
if(tmp<=ans)
continue;
ans=tmp;
break;
}
f[st][ed][len]=ans;
return ans;
}
int main()
{
int T,t,cnt,i,n,Cas=1;
scanf("%d",&T);
while(T--)
{
memset(a,0,sizeof(a));
scanf("%d",&n);
scanf("%d",&t);
cnt=0;
a[cnt].c=t;
a[cnt].n=1;
for(i=1;i<n;i++)
{
scanf("%d",&t);
if(t==a[cnt].c)
{
a[cnt].n++;
}
else
{
cnt++;
a[cnt].c=t;
a[cnt].n=1;
}
}
memset(f,0,sizeof(f));
printf("Case %d: %d
",Cas++,work(0,cnt,0));
}
return 0;
}
poj1390blocks动态规划
BlocksTimeLimit:?5000MS?MemoryLimit:?65536KTotalSubmissions:?4173?Accepted:?1661DescriptionSomeofyoumayhaveplayedagamecalled‘Blocks‘.Therearenblocksinarow,eachboxhasacolor.Hereisanexample:Gold,Silver, 查看详情
poj-1390blocks区间dp
BlocksTimeLimit: 5000MS MemoryLimit: 65536KTotalSubmissions: 5252 Accepted: 2165DescriptionSomeofyoumayhaveplayedagamecalled‘Blocks‘.Therearenblocksinarow,eachboxhasacolo 查看详情
三维dp--poj1390--blocks(代码片段)
题意介绍初看这道题，想了想没头绪，感觉又要被虐了，按照《算法基础》郭老师的讲解，勉强接受了这个奇怪的状态转移方程，但是还是感觉很吃力，照着视频写了一遍之后，又去网上看了看别人的代码，我的天哪，比郭老师... 查看详情
poj2111milleniumleapcow(记忆化搜索）
DescriptionThecowshaverevisedtheirgameofleapcow.TheynowplayinthemiddleofahugepastureuponwhichtheyhavemarkedagridthatbearsaremarkableresemblancetoachessboardofNrowsandNcolumns(3<=N<=365). He 查看详情
poj1390blocks（dp+思维）题解(代码片段)
题意：有一排颜色的球，每次选择一个球消去，那么这个球所在的同颜色的整段都消去（和消消乐同理），若消去k个，那么得分k*k，问你消完所有球最大得分思路：显然这里我们直接用二位数组设区间DP行不通，我们不能表示出... 查看详情
poj1661helpjimmy（记忆化搜索）
题目链接：http://poj.org/problem?id=1661一道还可以的记忆化搜索题，主要是要想到如何设dp，记忆化搜索是避免递归过程中的重复求值，所以要得到dp必须知道如何递归由于这是个可以左右移动的所以递归过程肯定设计左右所以dp的一... 查看详情
poj1351numberoflocks（记忆化搜索）
题目链接：传送门思路：这道题是维基百科上面的记忆化搜索的例题。。。四维状态dp[maxn][5][2][5]分别表示第几根棒子，这根棒子的高度，是否达到题目的要求和使用不同棒子数。那么接下来就是状态转移了。。。要用到位运算... 查看详情
poj1390block
DescriptionSomeofyoumayhaveplayedagamecalled‘Blocks‘.Therearenblocksinarow,eachboxhasacolor.Hereisanexample:Gold,Silver,Silver,Silver,Silver,Bronze,Bronze,Bronze,Gold. Thecorrespondingpictu 查看详情
poj1179区间dp（记忆化搜索写法）有巨坑！
http://poj.org/problem?id=1179DescriptionPolygonisagameforoneplayerthatstartsonapolygonwithNvertices,liketheoneinFigure1,whereN=4.Eachvertexislabelledwithanintegerandeachedgeislabelledwitheitherthesym 查看详情
记忆化搜索||poj1088滑雪
...数那里走，问最远长度是多少*解法：每一点dfs搜索一遍记忆化搜索：http://blog.csdn.net/acmer_sly/article/details/53440798递归：求解的方法都是相同的（距离是周围的点最大值加一），假设已知周围点的距离则dd[i]=dfs(xx,yy)+1; 每一次递... 查看详情
poj1579functionrunfun记忆化搜索入门(代码片段)
题目传送门：http://poj.org/problem?id=1579FunctionRunFunTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 20560 Accepted: 10325DescriptionWeallloverecursion!Don‘twe? 查看详情
poj1088滑雪（记忆化搜索）
滑雪TimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 92384 Accepted: 34948DescriptionMichael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次... 查看详情
poj1191棋盘切割（压缩dp+记忆化搜索）
一，题意：中文题二。分析：主要利用压缩dp与记忆化搜索思想三，代码：#include<iostream>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>usingnamespacestd;constintBig=20000000;intMat[10] 查看详情
poj1088滑雪记忆化搜索
解析：状态d[i][j]代表r=i,c=j这个位置能滑的最大长度。深搜+备忘录#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;constintmaxn=100+5;intR,C;inta[maxn][maxn];intd[m 查看详情
poj2704pascal'stravelsdfs记忆化搜索(代码片段)
题目传送门：http://poj.org/problem?id=2704Pascal‘sTravelsTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 5535 Accepted: 2500DescriptionAnnxngameboardispopulatedwithinteg 查看详情
poj_1088_(dp)(记忆化搜索)
滑雪TimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 95792 Accepted: 36322DescriptionMichael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次... 查看详情
poj1088:滑雪（经典dp+记忆化搜索）
滑雪TimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 74996 Accepted: 27818DescriptionMichael喜欢滑雪百这并不奇怪，由于滑雪的确非常刺激。但是为了获得速度，滑的区域必须向下倾斜，并且当你滑到坡底，你不得不再... 查看详情
poj1664dp记忆化搜索
http://poj.org/problem?id=1664Description把M个相同的苹果放在N个相同的盘子里，同意有的盘子空着不放，问共同拥有多少种不同的分法？（用K表示）5。1。1和1。5，1是同一种分法。Input第一行是測试数据的数目t（0<=t<=20）。下面每... 查看详情