Codeforces Round #369 (Div. 2) C. Coloring Trees(简单dp)

题目:https://codeforces.com/problemset/problem/711/C

题意:给你n,m,k,代表n个数的序列,有m种颜色可以涂,0代表未涂颜色,其他代表已经涂好了,连着一段是相同颜色的是一个连通块,求正好有k个连通块的最小花费

思路:首先每个位置有可能有m中颜色,而且要满足k个,我们我们可以推出所有情况

dp[n][m][k]

n代表前n个数

m代表当前涂m色

k代表满足k个了

Codeforces Round #369 (Div. 2)     C. Coloring Trees(简单dp)

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#define mod 1000000007
#define maxn 200005
#define INF 100000000000000+10
using namespace std;
typedef long long ll;
ll n,m,k;
ll a[];
ll c[][];
ll dp[][][];
int main()
{
cin>>n>>m>>k;
for(int i=;i<=n;i++){
cin>>a[i];
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
cin>>c[i][j];
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
for(int z=;z<=k;z++)
dp[i][j][z]=INF;
}
}
if(a[]){
dp[][a[]][]=;
}
else{
for(int j=;j<=m;j++){
dp[][j][]=c[][j];
}
}
for(int i=;i<=n;i++)
{
if(!a[i])//不是0的时候
{
for(int j=;j<=m;j++)
for(int k=;k<=i;k++)
for(int h=;h<=m;h++)
{
if(j==h)
dp[i][j][k]=min(dp[i][j][k],dp[i-][h][k]+c[i][j]);//颜色相同情况
else
dp[i][j][k]=min(dp[i][j][k],dp[i-][h][k-]+c[i][j]);//颜色不相同
}
}
else
{
for(int k=;k<=i;k++)
for(int h=;h<=m;h++)
{
if(a[i]==h)
dp[i][a[i]][k]=min(dp[i][a[i]][k],dp[i-][a[i]][k]);//同上
else
dp[i][a[i]][k]=min(dp[i][a[i]][k],dp[i-][h][k-]);
}
}
}
ll mn=INF;
for(int i=;i<=m;i++){
mn=min(mn,dp[n][i][k]);
}
if(mn>=INF) printf("-1");
else cout<<mn;
}
上一篇:使用Mac为三台CentOS7配置Java


下一篇:css 强制换行