专业做网站的技术人员,互联网舆情监测中心待遇,网站建设脑图,衡水做淘宝网站建设题目描述 小明需要在一篇文档中加入 N 张图片#xff0c;其中第 i 张图片的宽度是 Wi#xff0c;高度是 Hi。 假设纸张的宽度是 M#xff0c;小明使用的文档编辑工具会用以下方式对图片进行自动排版#xff1a; 1. 该工具会按照图片顺序#xff0c;在宽度 M 以内… 题目描述 小明需要在一篇文档中加入 N 张图片其中第 i 张图片的宽度是 Wi高度是 Hi。 假设纸张的宽度是 M小明使用的文档编辑工具会用以下方式对图片进行自动排版 1. 该工具会按照图片顺序在宽度 M 以内将尽可能多的图片排在一行。该行的高度是行内最高的图片的高度。例如在 M10 的纸张上依次打印 3x4, 2x2, 3x3 三张图片则效果如下图所示这一行高度为4。(分割线以上为列标尺分割线以下为排版区域数字组成的矩形为第x张图片占用的版面) 2. 如果当前行剩余宽度大于0并且小于下一张图片则下一张图片会按比例缩放到宽度为当前行剩余宽度(高度向上取整)然后放入当前行。例如再放入一张4x9的图片由于剩余宽度是2这张图片会被压缩到2x5再被放入第一行的末尾。此时该行高度为5 3. 如果当前行剩余宽度为0该工具会从下一行开始继续对剩余的图片进行排版直到所有图片都处理完毕。此时所有行的总高度和就是这 N 张图片的排版高度。例如再放入11x1, 5x5, 3x4 的图片后效果如下图所示总高度为11 现在由于排版高度过高图片的先后顺序也不能改变小明只好从 N 张图片中选择一张删除掉以降低总高度。他希望剩余N-1张图片按原顺序的排版高度最低你能求出最低高度是多少么 输入 第一行包含两个整数 M 和 N分别表示纸张宽度和图片的数量。 接下来 N 行每行2个整数Wi, Hi表示第 i 个图大小为 Wi*Hi。 对于30%的数据满足1N1000 对于100%的数据满足1N1000001M, Wi, Hi100 输出 一个整数表示在删除掉某一张图片之后排版高度最少能是多少。 样例输入1 4 3 2 2 2 3 2 2 样例输出1 2 思路要删去一张图片使高度最小无非是遍历N张图片判断第i个图片不选是否拥有更小的高度。
可以分割一下状态例如第i行中图片j判断不选图片j的高度可以由三个状态组成
①前i-1行的总高度这是固定的在遍历过程就可以知道
②i1行以后的总高度这个要怎么得到呢可以知道i1行开头肯定是新的照片k我从那张照片k开始遍历到最后一张照片所得的高度一定是确定的可以设置一个数组t[i]保留i照片以及以后的高度。
③此时不选j第i行的高度想要求这个可以定义一个calc函数实现向行中添加图片直到添加完全部图片或者宽度已达最大求出该行的高度再加上t[i]就成了第i行以及以后所有行的总高度为了实现calc函数还得定义一个solve函数solve函数的目的是判断加了一张图片该行的宽度和高度变化。
很明显用了动态规划的思想他有状态转移关系问题被细分为了多个子问题把处理全部细分为了处理行。
这种方法适用于一些题目题目中总体只修改了部分结构只需要处理那部分被修改的状态其余的部分可以通过处理得到视为常量。
代码如下
#includebits/stdc.h
using namespace std;
const int N1e510;
int m,n,h[N],w[N],t[N];
void solve(int i,int W,int H){if(Ww[i]m){ Hmax(H,h[i]); }else{Hmax(H,(h[i]*(m-W)w[i]-1)/w[i]);}Wmin(m,Ww[i]);
}
int calc(int i,int W,int H){while(inWm)solve(i,W,H); return Ht[i];
}
int main(){cinmn;for(int i0;in;i)cinw[i]h[i];for(int in-1;i0;i--)t[i]calc(i,0,0);int rest[0],pre_h0,W0,H0;for(int i0;in;i){int tmpcalc(i1,W,H);resmin(res,pre_htmp);solve(i,W,H);if(Wm)pre_hH,W0,H0;} coutresendl;
}
加了注释后
#includebits/stdc.h
using namespace std;
const int N1e510;
int m,n,h[N],w[N],t[N];//m为每行最大宽度n为图片数量h为每张图片对应高度w为每张图片对应宽度t[i]为以i图片为开始与他以后所有的图片组合形成的最小高度一定是以i为行头开始
void solve(int i,int W,int H){//找出加入i元素后该行的高度和宽度所发生的变化 if(Ww[i]m){//没超出最大宽度 Hmax(H,h[i]); }else{Hmax(H,(h[i]*(m-W)w[i]-1)/w[i]);//为什么要加w[i]-1因为他要向上取整所以要加一个小数即(w[i]-1)/w[i]}Wmin(m,Ww[i]);
}
int calc(int i,int W,int H){//求出加入i以及他后边所有图片后总高度的变化 while(inWm)solve(i,W,H);//只要算一行的另起一行的可以直接由t[i]得到 return Ht[i];//为什么这里是Ht[i]因为之前的一行可能已经有照片了我先填满那一行拿到那一行的高度即H然后之后的元素就另起一行了对应t[i],所以t[i]是需要预处理的所以总的高度为Ht[i]
}
int main(){cinmn;for(int i0;in;i)cinw[i]h[i];for(int in-1;i0;i--)t[i]calc(i,0,0);//W0H0说明要求的是以i照片开头的与它以后所有的图片组合形成的最小高度预处理阶段不预处理以后可能有重复的求解过程int rest[0],pre_h0,W0,H0;//res先取t[0]是代表所有图片都取了后它的高度 pre_h为 之前已经统计了的行的高度正在统计的不算 for(int i0;in;i){int tmpcalc(i1,W,H);//计算出加入i1以及之后的所有图片后总高度的变化不包括i这就对应了删除一张图片的思想 resmin(res,pre_htmp);//前者为之前统计出的最小高度后者为不要i照片的最小高度 solve(i,W,H);//加入i照片if(Wm)pre_hH,W0,H0;//此时已经充满一行那就得另起一行了所以pre_h要HH和W要清零 } coutresendl;
}
