Codeforces Round #369 (Div. 2)-C Coloring Trees

题目大意:有n个点,由m种颜料,有些点没有涂色,有些点已经涂色了,告诉你每个点涂m种颜色的价格分别是多少,

让你求将这n个点分成k段最少需要多少钱。

思路:动态规划,我们另dp[ i ][ j ][ k ] 表示到i个点为止,分成j段,最后一段的颜色为k的最少值,然后就能很容易地

写出状态转移方程。

 #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll dp[N][N][N],c[N],cost[N][N];
int n,m,k;
int main()
{
memset(dp,inf,sizeof(dp));
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++) scanf("%lld",&c[i]);
for(int i=;i<=m;i++) dp[][][i]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++) scanf("%lld",&cost[i][j]);
}
for(int i=;i<=n;i++)
{
for(int j=;j<=k;j++)
{
for(int u=;u<=m;u++)
{
if(c[i] && u!=c[i]) continue;
for(int v=;v<=m;v++)
{
if(u==v) dp[i][j][u]=min(dp[i][j][u],dp[i-][j][v]);
else dp[i][j][u]=min(dp[i][j][u],dp[i-][j-][v]);
}
if(!c[i]) dp[i][j][u]+=cost[i][u];
}
}
}
ll ans=inf;
for(int i=;i<=m;i++) ans=min(ans,dp[n][k][i]);
printf("%lld\n",ans==inf? -:ans);
return ;
}
上一篇:Java中static、final用法小结(转)


下一篇:Codeforces #369 (Div. 2) C. Coloring Trees (3维dp