Joyoi花店橱窗(原tyvj1124)
2024-10-18 03:33:52
题目:http://www.joyoi.cn/problem/tyvj-1124
两点注意!!!
1.滚动数组的初始化;
2.字典序操作!
感到很有趣!!!
#include<iostream>
#include<cstdio>
using namespace std;
const int INF=-0x7fffffff;
int n,m,pos[][],pre[][],ans[];
long long a[][],d[][],mx=INF;
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%lld",&a[i][j]);
for(int i=;i<=m;i++)
{
if(a[][i]>mx)
{
mx=a[][i];
pos[][i]=i;
}
else pos[][i]=pos[][i-];
d[][i]=mx;
}
for(int i=;i<=n;i++)
{
d[i%][i-]=INF;//////因为是滚动数组,故初始化memset INF有漏洞 ,且i+1的时候不会用到这里了,可放心
for(int j=i;j<=m-(n-i);j++)
{
if(d[i%][j-]>=d[(i-)%][j-]+a[i][j])//////字典序
{
d[i%][j]=d[i%][j-];
pos[i][j]=pos[i][j-];
pre[i][j]=pre[i][j-];
}
else
{
d[i%][j]=d[(i-)%][j-]+a[i][j];
pos[i][j]=j;
pre[i][j]=pos[i-][j-];
}
}
}
printf("%lld\n",d[n%][m]);
int k=pos[n][m];
for(int i=n;i;i--)
{
// while(a[i][k-1]==a[i][k])k--;//////字典序 (不行!会过头……)
ans[i]=k;
k=pre[i][k];
}
for(int i=;i<=n;i++)
printf("%d ",ans[i]);
return ;
}
最新文章
- ASP.NET MVC 使用 Petapoco 微型ORM框架+NpgSql驱动连接 PostgreSQL数据库
- leetcode371. Sum of Two Integers
- CSS布局——居中
- Force.com微信企业号开发系列(一) - 启用二次验证
- POJ 2442 Sequence
- Android基础总结
- 图像JPEG格式介绍
- EntityFramework.Extended扩展用法
- Windows 中JDK安装配置教程
- 变态最大值(nyoj)
- webview h5页面 关闭
- laravel5.5 when()的用法
- The 14th tip of DB Query Analyzer
- 适用于Mac 的自动补丁管理软件
- python干掉pycache
- 2019热门JAVA面试问题
- C语言编程—自动生成四则运算升级版
- python文件操作-r、w、a、r+、w+、a+和b模式
- 解决Ubuntu14.04 下 E: Encountered a section with no Package: header 问题
- Python常见初级错误