【链接】 我是链接,点我呀:)
【题意】
在这里输入题意
【题解】
f[i][j][k]前i个位置,第i个位置放j这个颜色,然后形成了k个联通块的最小花费
分第i个位置有没有已经放颜色两种情况考虑。
如果有放的话。枚举前一个位置的颜色以及前i-1个位置形成的联通块的数目
如果没有放的话。枚举当前以及前一个的颜色以及前i-1个位置形成的联通块数目
有放不用加代价。
没有放的话加上放的代价就会。
最后在f[n][1..m][k]里面找最小值
【代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int n,m,k,c[N+10],p[N+10][N+10];
long long f[N+10][N+10][N+10];
void get_min(long long &x,long long y){
if (x==-1) x = y;
if (y<x) x = y;
}
int main()
{
#ifdef LOCAL_DEFINE
freopen("D:\\rush.txt","r",stdin);
#endif // LOCAL_DEFINE
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> m>>k;
for (int i = 1;i <= n;i++) cin >> c[i];
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
cin >> p[i][j];
memset(f,255,sizeof f);
f[0][0][0] = 0;
for (int i = 1;i <= n;i++){
if (c[i]!=0){
//第i个位置的颜色已经固定。
//枚举前一个的颜色
for (int j = 0;j <= m;j++)
for (int k = 0;k <= i-1;k++)
if (f[i-1][j][k]!=-1){
if (j!=c[i]){
get_min(f[i][c[i]][k+1],f[i-1][j][k]);
}else{
get_min(f[i][c[i]][k],f[i-1][j][k]);
}
}
}else{
//这一个的颜色和前一个的颜色都要枚举
for (int j = 1;j <= m;j++)
for (int jj = 0;jj <= m;jj++)
for (int k = 0;k <= i-1;k++){
if (f[i-1][jj][k]!=-1){
if (j!=jj){
get_min(f[i][j][k+1],f[i-1][jj][k]+p[i][j]);
}else{
get_min(f[i][j][k],f[i-1][jj][k]+p[i][j]);
}
}
}
}
}
//f[n][1..m][k]
long long ans = -1;
for (int i = 1;i <= m;i++)
if (f[n][i][k]!=-1)
get_min(ans,f[n][i][k]);
cout<<ans<<endl;
return 0;
}