【HDU6212】Zuma

Source and Judge

HDU6212

Record

1h

Analysis

请先思考后再展开

好神仙啊,虽然正解看上去很简单

考试的时候一直往lrj之前一道经典区间dp方面想
然而这是一道分类讨论转移的dp题(当然依然要合并同颜色的块)

  1. 直接分两半
  2. 通过消除中间的,合并两边,两边代价是补上去的
  3. 消除两块,使3个合并起来,那么中间一定只能是1个

还有一种情况,但似乎不会是最优解?就是四个球,然后先分别消除两边,然后把2和2合并。但不知道怎么排除这种情况
另外,本题应该有非常多种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
// #define pr pair<int,int>
// #define FR first
// #define SE second
// #define MP make_pair
const int MAX_N=210;
char s[MAX_N];
int a[MAX_N],sz[MAX_N];
int f[MAX_N][MAX_N];
void chmin(int &x,int y){x=x>y?y:x;}
void main()
{
int T;scanf("%d",&T);s[0]='h';
for(int t=1;t<=T;t++)
{
scanf("%s",s+1);int m=strlen(s+1),n=0;
for(int i=1;i<=m;i++)
if(s[i-1]!=s[i]) a[++n]=s[i]-'0',sz[n]=1;
else sz[n]++;
memset(f,63,sizeof f);
for(int i=1;i<=n;i++) f[i][i]=3-sz[i];
for(int ln=2;ln<=n;ln++)
for(int l=1,r=l+ln-1;r<=n;l++,r++)
{
for(int k=l;k<r;k++) chmin(f[l][r],f[l][k]+f[k+1][r]);
int tot=sz[l]+sz[r];
if(a[l]==a[r]) chmin(f[l][r],f[l+1][r-1]+(tot>=3?0:3-tot));
if(a[l]==a[r] and tot<=3) for(int k=l+1;k<=r-1;k++)
if(sz[k]==1 and a[l]==a[k]) chmin(f[l][r],f[l+1][k-1]+f[k+1][r-1]);
}
printf("Case #%d: %d\n",t,f[1][n]);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/4279.html
转载请注明出处,谢谢!