问题描述：http://hihocoder.com/problemset/problem/1365 思路来源：http://blog.csdn.net/lubovbyc/article/details/52348812 声明：并非完全原创，思路完全借鉴上述大神。只是大神毕竟大神，寥寥数语便解决了问题，理解起来很费劲，所以写此博客，解释下大神的思路。 这个问题类似于动态规划问题，思路如下： （1）大思路是遍历每种可能，即一次去掉第0张图片，第1张…一直到最后一张图片，从而得出最小的高度； （2）为了满足时间性能的要求，定义一个数组t，t[i]表示从第i张图片重新开始进行排版的高度，这里重新的意思相当于剩余宽度为0我们另起一行进行排版； （3）解释下三个函数的作用：init()，这个明显，主要求出t[i]；attach(int i, int& w, int& h)就是在宽度为w，高度为h的情况下，再添加一张图片i更新w和h；cal(int i, int w, int h)就是计算剩余宽度为w，高度为h的情况下加上从第i张图片开始到最后的图片后的最终h。 解释下程序为什么能够求出结果： 首先去掉第0张，相当于求第一张到最后一张的排版高度，此时有cal(1,0,0)，返回的是t[1]；当i=k时，也就是去掉k张，则cal(k+1,w,h)表示在剩余宽度为w，高度为h下加上第k+i到最后一张的高度；当i=N-1，相当于求前N-2张图片排版高度，注意每次attach时就加上一张，故此时返回pre即可，pre表示前i-1张图片的排版高度。 附上代码：
#include<iostream> #include<vector> #include<algorithm> using namespace std; const int SIZE = 100005; const int INF = 0x3f3f3f3f; int M, N; vector<int> wi(SIZE, 0), hi(SIZE, 0), t(SIZE, 0); void attach(int i, int& w, int& h); int cal(int i, int w, int h); void init(); int main() { init(); int ans = INF, pre = 0, w = 0, h = 0,tmp=0; for (int i = 0;i < N;++i) { tmp = cal(i + 1, w, h); ans = min(ans, tmp + pre); attach(i, w, h); if (w == M) { pre += h; w=h = 0; } } cout << ans << endl; } int cal(int i, int w, int h) { while (i < N&&w < M) attach(i++, w, h); return h + t[i]; } void attach(int i, int& w, int& h) { if (w + wi[i] > M) h = max((int)ceil(1.0*hi[i] * (M-w) / wi[i]), h); else h = max(hi[i], h); w = min(M, w + wi[i]); } void init() { cin >> M >> N; for (int i = 0;i < N;++i) cin >> wi[i] >> hi[i]; for (int i = N - 1;i>=0;--i) t[i] = cal(i, 0, 0); }