711C - Coloring Trees - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=2e18+9;
int n,m,k,a[111],p[111][111],dp[111][111][111];
inline int dfs(int i,int j,int f){
	if(f>k)return inf;
	if(i==n)return (f==k?0:inf);
	if(~dp[i][j][f])return dp[i][j][f];
	int ans=inf;
	if(a[i])ans=dfs(i+1,a[i],f+(a[i]!=j));
	else for(int c=1;c<=m;++c)ans=min(ans,p[i][c-1]+dfs(i+1,c,f+(c!=j)));
	return dp[i][j][f]=ans;
}
signed main(){
	cin>>n>>m>>k;memset(dp,-1,sizeof(dp));
	for(int i=0;i<n;++i)cin>>a[i];
	for(int i=0;i<n;++i)for(int j=0;j<m;++j)cin>>p[i][j];
	cout<<(dfs(0,0,0)==inf?-1:dp[0][0][0])<<endl;
}