http://codeforces.com/group/1EzrFFyOc0/contest/711/problem/C

https://blog.csdn.net/qq_36368339/article/details/78568585?locationNum=6&fps=1  题解

题意:(真难理解)有n个点,m种颜色,你要给n个点上没有颜色的点染色。每个点i对应染的颜色j有一个颜料消耗,p[i][j]是点i染成j颜色的花费,你必须保证有k段颜色的点,输出最少花费多少颜料。

思路:题意稍微不太好理解。。。 
dp[i][j][v]:位置i染第j种颜料恰好有v段颜色,所花费的颜料数量; 
第i个位置没被染色:i已经确定,但j,v未知,需要暴力枚举。 
第i个位置已被染色:i,j已经确定,只需要暴力枚举v。(具体方程看代码) 
坑点就是初始化,还有注意找最小值。

 #include<iostream>
#include<cstdio>
#include <cctype>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<cmath>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
#define mem(a,x) memset(a,x,sizeof(a))
#define se second
#define fi first
const int INF= 0x3f3f3f3f;
const int N=1e6+; ll n,m,k,a[],p[][],dp[][][]; int main()
{
cin>>n>>m>>k;
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++) scanf("%d",&p[i][j]); for(int i=;i<=n;i++)
for(int u=;u<=m;u++)
for(int v=;v<=k;v++) dp[i][u][v]=1e18; if(a[]==){ //初始化 如果第一个点没被涂色
for(int i=;i<=m;i++)
dp[][i][]=p[][i]; //涂上第一个点对应的p[1][j] ,此时v=1
}
else{ //第一个点被涂色了
dp[][a[]][]=; //=0 ,因为这样的点 不计入结果
} for(int i=;i<=n;i++)
{
if(a[i]==)
{
for(int u=;u<=m;u++)
{
for(int v=;v<=k;v++)
{
//下面比较v不变的时候:
dp[i][u][v]=min(dp[i][u][v], dp[i-][u][v]+p[i][u] ); //下面比较v 变的时候:
for(int j=;j<=m;j++)
{
if(j!=u && v>)
dp[i][u][v]=min(dp[i][u][v],dp[i-][j][v-]+p[i][u] );
}
//通过以上 找出:对相同的i,在u在[1,m]和v在[1,k]范围内dp[i][u][v]的最小值
}
}
}
else{
for(int u=;u<=m;u++)
{
for(int v=;v<=k;v++)
{
dp[i][a[i]][v]=min(dp[i][a[i]][v],dp[i-][a[i]][v]);
for(int j=;j<=m;j++)
{
if(j!=a[i] && v>)
dp[i][a[i]][v]=min(dp[i][a[i]][v],dp[i-][j][v-]);
}
}
}
}
}
ll ans=1e18;
for(int i=;i<=m;i++)
ans=min(ans,dp[n][i][k]);
if(ans==1e18) cout<<-;
else cout<<ans<<endl;
}

最新文章

  1. [干货]Chloe官网及基于NFine的后台源码毫无保留开放
  2. cmake 出现问题
  3. 李洪强-C语言3-数组
  4. javaScript DOM编程
  5. Linux系统监视资源与进程管理
  6. 电商安全无小事,如何有效地抵御 CSRF 攻击?
  7. NOI2002银河英雄传说
  8. css3学习文档
  9. Easyui _treegrid 动态加载子节点
  10. java傻瓜简单100%一定看的懂新手安装教程
  11. HDU 1540 Tunnel Warfare(最长连续区间 基础)
  12. VUE 生成二维码(qrcodejs)
  13. SqlServer查询某个表的列名称、说明、备注、类型等
  14. suoi38 卖XY序列 (贪心+前缀和)
  15. HDU 5873 Football Games(竞赛图兰道定理)
  16. maven +IEDA+log4j
  17. Openstack_通用模块_Oslo_vmware 创建 vCenter 虚拟机快照
  18. HTTP2 概述
  19. 非super user管理会话
  20. 获取IP相关信息和文件上传

热门文章

  1. CSS网站框架及样式命名规范
  2. Data - 数据思维 - 中篇
  3. axios ajax框架 请求配置
  4. Flutter Bloc状态管理 简单上手
  5. 【GStreamer开发】GStreamer播放教程03——pipeline的快捷访问
  6. jira7.3.6 windows7下安装、中文及破解
  7. GATK4注意事项
  8. LINUX驱动笔记 目录
  9. 【SCALA】1、我要开始学习scala啦
  10. DataSource配置