在桌面从左至右横向摆放着 N 堆石子。
每一堆石子都有着相同的颜色，颜色可能是颜色 0，颜色 1 或者颜色 2 中的其中一种。
现在要对石子进行合并，规定每次只能选择位置相邻并且颜色相同的两堆石子进行合并。
合并后新堆的相对位置保持不变，新堆的石子数目为所选择的两堆石子数目之和，并且新堆石子的颜色也会发生循环式的变化。
具体来说：两堆颜色 0 的石子合并后的石子堆为颜色 1，两堆颜色 1 的石子合并后的石子堆为颜色 2，两堆颜色 2 的石子合并后的石子堆为颜色 0。
本次合并的花费为所选择的两堆石子的数目之和。
给出 N 堆石子以及他们的初始颜色，请问最少可以将它们合并为多少堆石子？
如果有多种答案，选择其中合并总花费最小的一种，合并总花费指的是在所有的合并操作中产生的合并花费的总和。
输入格式
第一行一个正整数 N 表示石子堆数。
第二行包含 N 个用空格分隔的正整数，表示从左至右每一堆石子的数目。
第三行包含 N 个值为 0 或 1 或 2的整数表示每堆石头的颜色。
输出格式
一行包含两个整数，用空格分隔。
其中第一个整数表示合并后数目最少的石头堆数，第二个整数表示对应的最小花费。
数据范围
对于 30% 的评测用例，1≤N≤10。
对于 50% 的评测用例，1≤N≤50。
对于 100% 的评测用例，1≤N≤300，1≤ 每堆石子的数目 ≤1000。
输入样例：
5
5 10 1 8 6
1 1 0 2 2
输出样例：
2 44
样例解释
上图显示了两种不同的合并方式。
其中节点中标明了每一堆的石子数目，在方括号中标注了当前堆石子的颜色属性。
左图的这种合并方式最终剩下了两堆石子，所产生的合并总花费为 15+14+15=44；右图的这种合并方式最终也剩下了两堆石子，但产生的合并总花费为 14+15+25=54。
综上所述，我们选择合并花费为 44 的这种方式作为答案。
题解：
使用区间DP，f[i][j][k]代表区间i-j之间颜色为k的合法情况，初始状态当i==j的时候，除自身颜色为0，即f[i][j][k]=0，其他为INF。
c[i][j]代表区间i-j之间能合并的最小堆数。
w[i][j]代表区间i-j之间的最小价值。
s[i]使用前缀和代表每个堆的价值以及区间的价值。
遍历长度，找出左边界和右边界，遍历区间，遍历颜色，当遇到左和右颜色相同的时候，合并，将c[i][j]设置为0，只有一个堆，重新赋值颜色以及合并后的价值。
注意：这里要重新循环一遍来更新最小的堆数和价值。
（代码参考了大佬的）
代码：
AC代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<set>
using namespace std;
typedef long long int ll;
const int INF=1e16;int n=0;
int minsize=1000001;
int minvalue=1000001;int change_color(int c){if(c==1){return 2;}else if(c==2){return 0;}else if(c==0){return 1;}
}void solve(int n){int c[305][305];int w[305][305];int v[305][305];int f[305][305][3];int s[305];//初始化for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){c[i][j]=j-i+1;if(i!=j){w[i][j]=INF;}for(int k=0;k<3;k++){f[i][j][k]=INF;}}}for(int i=1;i<=n;i++){int t;cin >> t;s[i]=s[i-1]+t;}for(int i=1;i<=n;i++){int t;cin >> t;f[i][i][t]=0;}for(int len=1;len<=n;len++){for(int l=1;l+len-1<=n;l++){int r=l+len-1;for(int i=0;i<3;i++){int a=INF;for(int j=l;j<r;j++){if(f[l][j][i]!=INF && f[j+1][r][i]!=INF){a=min(a,f[l][j][i]+f[j+1][r][i]);}}if(a!=INF){c[l][r]=1;f[l][r][(i+1)%3]=min(f[l][r][(i+1)%3],a+s[r]-s[l-1]);w[l][r]=min(w[l][r],f[l][r][(i+1)%3]);}}for(int j=l;j<r;j++){if(c[l][r]>c[l][j]+c[j+1][r]){c[l][r]=c[l][j]+c[j+1][r];w[l][r]=w[l][j]+w[j+1][r];}else if(c[l][r]==c[l][j]+c[j+1][r]){w[l][r]=min(w[l][r],w[l][j]+w[j+1][r]);}}}}cout<<c[1][n]<<' '<<w[1][n];
}int main(){cin >> n;solve(n);//cout << minsize << " " << minvalue;
}
TLE代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<set>
using namespace std;
typedef long long int ll;int n=0;
int minsize=1000001;
int minvalue=1000001;int change_color(int c){if(c==1){return 2;}else if(c==2){return 0;}else if(c==0){return 1;}
}void dfs(int now,int now_value,int n,vector<int> v,vector<int> c){//checkif(now==c.size()-1){//cout << c.size() << " " << now_value << "\n";if(c.size()<minsize){minsize=c.size();minvalue=now_value;}else if(c.size()==minsize && now_value<minvalue){minvalue=now_value;}return;}//nodfs(now+1,now_value,n,v,c);//yesif(now<c.size()-1 && c[now]==c[now+1]){int value=v[now]+v[now+1];int color=change_color(c[now]);v.erase(v.begin()+now);v.erase(v.begin()+now);c.erase(c.begin()+now);c.erase(c.begin()+now);v.insert(v.begin()+now,value);c.insert(c.begin()+now,color);dfs(0,now_value+value,n,v,c);}
}int main(){cin >> n;vector<int> v;vector<int> c;for(int i=0;i<n;i++){int t;cin >> t;v.push_back(t);}for(int i=0;i<n;i++){int t;cin >> t;c.push_back(t);}dfs(0,0,n,v,c);cout << minsize << " " << minvalue;
}