Codeforces Round #241 (Div. 2) B dp
1 second
256 megabytes
standard input
standard output
A well-known art union called "Kalevich is Alive!" manufactures objects d'art (pictures). The union consists of n painters who decided to organize their work as follows.
Each painter uses only the color that was assigned to him. The colors are distinct for all painters. Let's assume that the first painter uses color 1, the second one uses color 2, and so on. Each picture will contain all these n colors. Adding the j-th color to the i-th picture takes the j-th painter tij units of time.
Order is important everywhere, so the painters' work is ordered by the following rules:
- Each picture is first painted by the first painter, then by the second one, and so on. That is, after the j-th painter finishes working on the picture, it must go to the (j + 1)-th painter (if j < n);
- each painter works on the pictures in some order: first, he paints the first picture, then he paints the second picture and so on;
- each painter can simultaneously work on at most one picture. However, the painters don't need any time to have a rest;
- as soon as the j-th painter finishes his part of working on the picture, the picture immediately becomes available to the next painter.
Given that the painters start working at time 0, find for each picture the time when it is ready for sale.
The first line of the input contains integers m, n (1 ≤ m ≤ 50000, 1 ≤ n ≤ 5), where m is the number of pictures and n is the number of painters. Then follow the descriptions of the pictures, one per line. Each line contains n integers ti1, ti2, ..., tin (1 ≤ tij ≤ 1000), where tij is the time the j-th painter needs to work on the i-th picture.
Print the sequence of m integers r1, r2, ..., rm, where ri is the moment when the n-th painter stopped working on the i-th picture.
5 1
1
2
3
4
5
1 3 6 10 15
4 2
2 5
3 1
5 3
10 1
7 8 13 21 题意: n幅 m个画家 每个画家按照次序画 给出每个画家画每幅画的时间
对于同一幅画 画家s画完 画家s+1才能画
画家只能同一时间段画一幅画 当结束当前画后 就可以进行下幅画 或 等待下一幅画被前一个画家画完才能画
问每一幅画被最后一个画家画完的时刻 题解: 动态规划处理 dp[i][j] 表示 第j个画家画完第i幅画的时刻
mp[i][j]代表 第j个画家画完第i幅画所需要的时间
转移方程 :
dp[i][j]=max(dp[i][j-1],dp[i-1][j])+mp[i][j]
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#define ll long long
#define mod 1e9+7
#define PI acos(-1.0)
#define bug(x) printf("%%%%%%%%%%%%%",x);
#define inf 1e8
using namespace std;
int n,m;
int mp[][];
int time[][];
int main()
{
scanf("%d %d",&n,&m);
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
scanf("%d",&mp[i][j]);
}
memset(time,,sizeof(time));
time[][]=mp[][];
for(int j=;j<=m;j++)
time[][j]=time[][j-]+mp[][j];
for(int j=;j<=n;j++)
time[j][]=time[j-][]+mp[j][];
for(int j=;j<=m;j++)
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(time[i-][j]>time[i][j-])
time[i][j]=time[i-][j]+mp[i][j];
else
time[i][j]=time[i][j-]+mp[i][j];
}
}
printf("%d",time[][m]);
for(int i=;i<=n;i++)
printf(" %d",time[i][m]);
printf("\n");
return ;
}
最新文章
- Chrome 开发者工具(DevTools)中所有快捷方式列表
- 四、jquery中的事件与应用
- [Web API] Web API 2 深入系列(7) Model绑定(下)
- error C2664: &#39;BOOL (PCERT_SELECT_STRUCT_A)&#39; : cannot convert parameter 1 from &#39;CERT_SELECT_STRUCT *&#39; to &#39;PCERT_SELECT_STRUCT_A&#39;
- Javascript中的字典和散列
- Comparable接口
- 用Python和摄像头制作简单的延时摄影
- MySQL基础(三)——约束
- JVM-类文件结构
- SQL Server锁、闩等资源的阻塞诊断---osql/sqlcmd,sp_blocker_pss80
- JS操作DOM元素属性和方法
- Android中连接蓝牙设备时遇到createRfcommSocketToServiceRecord的UUID问题和BluetoothSocket的connect失败
- java中对List中对象排序实现
- 【DataMagic】如何在万亿级别规模的数据量上使用Spark
- SpringMVC之Ajax与Controller交互
- 关于eclipse常用的一些快捷键
- Python中关于列表嵌套列表的处理
- vmvare使用桥接和NAT方式连接网络
- 安装 sshpass
- sklearn——数据集调用及应用
热门文章
- CUDA并行存储模型
- C#箴言之用属性来访问类的私有成员
- 已解决: mybatis报错 org.apache.ibatis.reflection.ReflectionException: There is no getter for property named &#39;xxx&#39; in &#39;class java.lang.String&#39;
- 项目10.2-企业级自动化运维工具---puppet详解
- Fakeapp 入门教程(2):使用篇!
- phpstrom怎样显示类的方法或函数列表
- 虚拟主机的搭建(ubuntu+apache2)
- float浮动布局(慕课网CSS笔记 + css核心技术详解第四章)
- 20.VUE学习之-变异方法push的留言版实例讲解
- python3中文件的读与写