uva 10239 The Book-shelver's Problem (dp)

Problem D The Book-shelver’s Problem
Input: standard input Output: standard output Time Limit: 5 seconds Memory Limit: 32 MB
 
You are given a collection of books, which must be shelved in a library bookcase ordered (from top to bottom in the bookcase and from left to right in each shelf) by the books’ catalogue numbers. The bookcase has a fixed width, but you may have any height you like. The books are placed on shelves in the bookcase in the usual upright manner (i.e., you cannot lay a book on its side). You may use as many shelves as you like, placed wherever you like up to the height of the bookcase, and you may put as many books on each shelf as you like up to the width of the bookcase. You may assume that the shelves have negligible thickness.
 
Now, given an ordered (by catalogue numbers) list of the heights and widths of the books and the width of the bookcase, you are expected to determinewhat is the minimum height bookcase that can shelve all those books.
 
Input
The input file may contain multiple test cases. The first line of each test case contains an integer N (1 £ N £ 1000) that denotes the number of books to shelve, and a floating-point number W (0 < W £ 1000) that denotes the width of the bookcase in centimeters. Then follow N lines where the i-th (1 £ i £N) line contains two floating-point numbers hi (0 < hi £ 100) and wi (0 < wi £ W) indicating the height and width (both in centimeters) of the i-th book in the list ordered by catalogue numbers. Each floating-point number will have four digits after the decimal point.
 
A test case containing two zeros for N and W terminates the input.
 
Output
For each test case in the input print a line containing the minimum height (in centimeters, up to four digits after the decimal point) of the bookcase that can shelve all the books in the list.
 
Sample Input
5 30.0000 30.0000 20.0000 20.0000 10.0000 25.0000 10.0000 30.0000 15.0000 10.0000 5.0000 10 20.0000 10.0000 2.0000 15.0000 10.0000 20.0000 5.0000 6.0000 2.0000 10.0000 3.0000 30.0000 6.0000 5.0000 3.0000 35.0000 2.0000 32.0000 4.0000 10.0000 6.0000 0 0.0000
 
Sample Output
60.0000 65.0000
(World Finals Warm-up Contest, Problem setter: Rezaul Alam Chowdhury)
 
"Even the darkest clowd has a silver lining."
이 문제 괜찮다!생각하기 시작한 상태는 dp[i][j]로 첫 번째 i개를 넣을 때 이 줄에 j의 넓이가 있음을 나타낸다. 첫 번째 i개의 최소값을 넣는다.그리고 이 문제는 폭이 부동점수라서 할 수가 없어요. 폭을 10000배로 늘리면 시간을 초과해요.다음 문제풀이를 찾아보니 다른 사람이 직접 dp[i]로 첫 번째를 이 줄의 첫 번째에 두었을 때 뒤에 모두 놓는 최소한의 대가를 나타낸다.이렇게 해서 i개를 놓고 뒤에 이 줄에 놓는 것을 고려하면 모든 방전의 가능성을 옮길 수 있다.

#include<cstdio>
#include<map>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<set>
#include<cmath>
using namespace std;
const int maxn = 1000 + 5;
const int INF = 1e9;
const double eps = 1e-6;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> P;
#define fi first
#define se second

double dp[maxn];
double h[maxn], w[maxn];
int n, get[maxn];
double width;

double dfs(int cur){
    if(get[cur])
        return dp[cur];
    if(cur >= n)
        return 0;
    if(cur == n-1)
        return h[n-1];
    get[cur] = 1;
    double ret = (double)INF;
    double height = h[cur], wid = w[cur];
    for(int i = cur+1;i <= n;i++){
        ret = min(ret, dfs(i)+height);
        height = max(height, h[i]);
        wid += w[i];
        if(wid-width>eps)
            break;
    }
    return dp[cur] = ret;
}

int main(){
    while(cin >> n >> width){
        if(n == 0 && width < eps)
            break;
        for(int i = 0;i < n;i++){
            cin >> h[i] >> w[i];
        }
        memset(get, 0, sizeof get);
        printf("%.4lf
", dfs(0));
    }
    return 0;
}