首页 > ACM题库 > HDU-杭电 > hdu 1971 The Bookcase-动态规划[解题报告]C++
2013
12-26

hdu 1971 The Bookcase-动态规划[解题报告]C++

The Bookcase

问题描述 :

No wonder the old bookcase caved under the massive piles of books Tom had stacked on it. He had better build a new one, this time large enough to hold all of his books. Tomfinds it practical to have the books close at hand when he works at his desk. Therefore, he is imagining a compact solution with the bookcase standing on the back of the desk. Obviously, this would put some restrictions on the size of the bookcase, it should preferably be as small as possible. In addition, Tom would like the bookcase to have exactly three shelves for aesthetical reasons.

Wondering how small his bookcase could be, he models the problem as follows. He measures
the height hi and thickness ti of each book i and he seeks a partition of the books in three non-empty sets S1, S2, S3 such that is minimized, i.e. the area of the bookcase as seen when standing in front of it (the depth needed is obviously the largest width of all his books, regardless of the partition). Note that this formula does not give the exact area of the bookcase, since the actual shelves cause a small additional height, and the sides cause a small additional width. For simplicity, we will ignore this small discrepancy.

Thinking a moment on the problem, Tom realizes he will need a computer program to do the job.

输入:

The input begins with a positive number on a line of its own telling the number of test cases (at most 20). For each test case there is one line containing a single positive integer N, 3 <= N <= 70 giving the number of books. Then N lines follow each containing two positive integers hi, ti, satisfying 150 <= hi <= 300 and 5 <= ti <= 30, the height and thickness of book i respectively, in millimeters.

输出:

The input begins with a positive number on a line of its own telling the number of test cases (at most 20). For each test case there is one line containing a single positive integer N, 3 <= N <= 70 giving the number of books. Then N lines follow each containing two positive integers hi, ti, satisfying 150 <= hi <= 300 and 5 <= ti <= 30, the height and thickness of book i respectively, in millimeters.

样例输入:

2
4
220 29
195 20
200 9
180 30
6
256 20
255 30
254 15
253 20
252 15
251 9

样例输出:

18000
29796

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;

#define INF 0x3f3f3f3f
#define MAXN 100
int dp[2][30*70+10][30*70+10];
int n;

struct book
{
    int t,h;
}a[MAXN];

bool cmp(book a,book b)
{
    return a.h>b.h;
}

int main()
{
    int cs;
    cin>>cs;
    while(cs--)
    {
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i].h>>a[i].t;
        sort(a,a+n,cmp);
        int cur=0;
        int sumt=0,sumh=0;
        memset(dp,-1,sizeof(dp));
        dp[cur][0][0]=0;
        for(int i=0;i<n;i++)
        {
            sumt+=a[i].t;
            for(int j=sumt;j>=0;j--)
            {
                for(int k=sumt-j;k>=0;k--)
                {
                    if(j+k==sumt-a[i].t && dp[cur][j][k]!=-1)
                        dp[cur^1][j][k]=dp[cur][j][k]+a[i].h;
                    else if(dp[cur][j][k]!=-1)
                        dp[cur^1][j][k]=dp[cur][j][k];
                    else
                        dp[cur^1][j][k]=-1;
                    if(j>=a[i].t && dp[cur][j-a[i].t][k]!=-1)
                    {
                        if(dp[cur^1][j][k]==-1)
                            dp[cur^1][j][k]=INF;
                        if(j==a[i].t)
                            dp[cur^1][j][k]=min(dp[cur^1][j][k],dp[cur][j-a[i].t][k]+a[i].h);
                        else
                            dp[cur^1][j][k]=min(dp[cur^1][j][k],dp[cur][j-a[i].t][k]);
                    }
                    if(k>=a[i].t && dp[cur][j][k-a[i].t]!=-1)
                    {
                        if(dp[cur^1][j][k]==-1)
                            dp[cur^1][j][k]=INF;
                        if(k==a[i].t)
                            dp[cur^1][j][k]=min(dp[cur^1][j][k],dp[cur][j][k-a[i].t]+a[i].h);
                        else
                            dp[cur^1][j][k]=min(dp[cur^1][j][k],dp[cur][j][k-a[i].t]);
                    }
                }
            }
            cur^=1;
        }
        int ans=0x3f3f3f3f;
        for(int i=sumt;i>0;i--)
            for(int j=sumt-i;j>0;j--)
            {
                if(dp[cur][i][j]==-1) continue;
                int k=sumt-j-i;
                if(k==0) continue;
                k=max(i,max(j,k));
                ans=min(ans,dp[cur][i][j]*k);
            }
        cout<<ans<<endl;
    }
    return 0;
}

 


  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  3. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  4. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  5. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的