题目传送门：http://codeforces.com/problemset/problem/1038/E
题意：给出$N$个方块，每个方块有左右两种颜色$a,b$（可以翻转使左右两种颜色交换）和一个权值$w$。当某个方块的右侧颜色与另一个方块的左侧颜色相同，它们可以连成一个大块，一个大块可以由若干个小块像这样连成（一个大块中可以只包含一个小块）。定义大块的权值为组成它的所有小块的权值和，问可以连成的大块中最大的权值。$N \leq 100 , a , b \leq 4 , w \leq 10^5$
看到$a,b \leq 4$就是神题预定
方法一：搜索
将四种颜色看做点，方块是连接左右两种颜色的边，就可以得到一个边为$100$，点为$4$的图，目标是找到一个边权和最大的简单路。然后我们可以发现图上很多的边是没有意义的。比如：
①某个方块左右两侧同色（在图上表示自环），这样子的边权直接算作点权即可。
②很多方块左右颜色相同（在图上表示重边），因为这些过多的重边可以通过在两个端点不断绕环，所以在搜索的时候经过它们很多次是没有必要的，所以考虑根据奇偶性将边数大于$3$的重边压成边数为$3$或者$2$（考试的时候想的是$2$或$1$但是考虑边为奇数的也有可能最后丢掉一条边到另外的颜色，所以必须留下$2$或$3$条），其中$2$或$1$条为原来最短边和次短边/最短边，而剩下的一条边则为其他重边压成的边，边权为它们的和。
经过这两种处理，图上的边的数量变为了最多$18$条，搜索可以承受（而且跑得贼快）。
#include<bits/stdc++.h>
using namespace std;
vector < ][];
] , cnt[][] , N , ans;
bool cmp(int a , int b){
return a > b;
}
void dfs(int now , int cnt){
int k = pri[now];
cnt += pri[now];
pri[now] = ;
; i <= ; i++)
if(!Edge[now][i].empty()){
];
Edge[now][i].erase(Edge[now][i].begin());
Edge[i][now].erase(Edge[i][now].begin());
dfs(i , cnt + t);
Edge[now][i].insert(Edge[now][i].begin() , t);
Edge[i][now].insert(Edge[i][now].begin() , t);
}
ans = max(ans , cnt);
pri[now] += k;
}
int main(){
cin >> N;
; i <= N ; i++){
int a , b , c;
cin >> a >> b >> c;
swap(b , c);
if(a == b)
pri[a] += c;
else{
Edge[a][b].push_back(c);
Edge[b][a].push_back(c);
cnt[a][b]++;
cnt[b][a]++;
}
}
; i <= ; i++)
; j <= ; j++){
sort(Edge[i][j].begin() , Edge[i][j].end() , cmp);
)
){
, p = Edge[i][j][cnt[i][j] - ] , q = Edge[i][j][cnt[i][j] - ];
; k < cnt[i][j] - ; k++)
sum += Edge[i][j][k];
Edge[i][j].clear();
Edge[i][j].push_back(sum);
Edge[i][j].push_back(p);
Edge[i][j].push_back(q);
}
else{
, p = Edge[i][j][cnt[i][j] -];
; k < cnt[i][j] - ; k++)
sum += Edge[i][j][k];
Edge[i][j].clear();
Edge[i][j].push_back(sum);
Edge[i][j].push_back(p);
}
}
; i <= ; i++)
dfs(i , );
cout << ans;
;
}
方法二：DP
设$f_{i,j,k,l}$表示选择$i$到$j$段的方块，大块左端颜色为$k$，右端颜色为$r$的时候获得的最大权值，考虑转移：
①由其中两段拼接而成：$f_{i,p,k,q}+f_{p+1,j,q,l}$
②由其中两段换位拼接而成（因为本身方块的拼接是无序的）：$f_{i,p,q,l}+f_{p+1,j,k,q}$
③只取左边一部分或者右边一部分：$f_{i,p,k,l}$或$f_{p,j,k,l}$
注意非法转移情况要用极小值覆盖，所以才有③转移才会产生最优值的情况。
#include<bits/stdc++.h>
using namespace std;
][][][] , l[] , r[] , w[];
int main(){
int N;
cin >> N;
; i <= N ; i++)
cin >> l[i] >> w[i] >> r[i];
memset(dp , -0x3f , sizeof(dp));
; i <= N ; i++)
dp[i][i][l[i]][r[i]] = dp[i][i][r[i]][l[i]] = w[i];
; i ; i--)
; j <= N ; j++)
; p <= ; p++)
; q <= ; q++)
for(int k = i ; k < j ; k++){
dp[i][j][p][q] = max(dp[i][j][p][q] , max(dp[i][k][p][q] , dp[k + ][j][p][q]));
; l <= ; l++)
dp[i][j][p][q] = max(dp[i][j][p][q] , max(dp[i][k][p][l] + dp[k + ][j][l][q] , dp[i][k][l][q] + dp[k + ][j][p][l]));
}
;
; i <= ; i++)
; j <= ; j++)
all = max(all , dp[][N][i][j]);
cout << all;
;
}