题解:CF1038E Maximum Matching_maximum matching csdn

题面

题目大意:
给你$n$个色块，每个色块两端分别有一种颜色，并且每个色块都有一个权值。

你可以将一个色块翻转。如果两个色块接触的两端颜色相同，就可以称这两个色块为一个序列，一个序列可能由多个色块构成，序列的值为所构成的色块值的和，求所有情况下所有序列的最大值

放在前面的话

这题应该是有两种做法

第一种是将块看成两个点和一条边，跑欧拉路径，使其路径上边的值最大。这种方法比较明显，但是实现起来可能有点困难，需要分类讨论比较多的细节，还需要判桥之类的。博主一开始写的是这种方法，结果调的一发不可收拾，于是扔了，换第二种做法。

第二种是暴力$dp$，数据范围这么小，不是摆明让你用暴力去水的吗？虽然第二种方法复杂度明显劣于第一种，但是它好打呀！更何况在$Div2$这种手速场，其实更加推荐本做法，也是博主最终写的做法

Sol

考虑最暴力的方式
$f[i][j][x][y]$表示用第$i$个到第$j$个之间的部分方块构成一个序列，序列左端颜色为$x$，右端颜色为$y$
然后就可以考虑$Floyed$式的转移
1.首先是使用中间的某些块
$$f[i][j][x][y]=maxf[i][k][x][p]+f[k+1][j][p][y]$$
2.然后因为允许将块左右短点颜色反转
$$f[i][j][x][y]=maxf[i][k][p][y]+f[k+1][j][x][p]$$
3.然后是不用中间的某些块
$$f[i][j][x][y]=maxf[i][k][x][y],f[k+1][j][x][y]$$
复杂度是$O(n\ast n\ast 4\ast 4\ast n\ast 4)$
然后我们就可以愉快的$AC$此题了虽然不是最优解

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int _=105;
inline int read()
{
	char ch='!';int z=1,num=0;
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')z=-1,ch=getchar();
	while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
	return z*num;
}
int n,f[_][_][5][5];
int main()
{
	n=read();
	memset(f,-63,sizeof(f));
	for(int i=1;i<=n;++i)
	{
		int a=read(),c=read(),b=read();
		f[i][i][a][b]=f[i][i][b][a]=c;
	}
	int ans=0;
	for(int i=n;i;--i)
		for(int j=i;j<=n;++j)
			for(int x=1;x<=4;++x)
				for(int y=1;y<=4;++y)
				{
					for(int k=i;k<=j+1;++k)
					{
						f[i][j][x][y]=max(f[i][j][x][y],max(f[i][k][x][y],f[k+1][j][x][y]));
						for(int p=1;p<=4;++p)
							f[i][j][x][y]=max(f[i][j][x][y],max(f[i][k][p][y]+f[k+1][j][x][p],f[i][k][x][p]+f[k+1][j][p][y]));
					}
					ans=max(ans,f[i][j][x][y]);
				}
	printf("%d\n",ans);
	return 0;
}

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
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