首页 > ACM题库 > HDU-杭电 > HDU 3127-WHUgirls-背包问题-[解题报告]HOJ
2014
03-03

HDU 3127-WHUgirls-背包问题-[解题报告]HOJ

WHUgirls

问题描述 :

There are many pretty girls in Wuhan University, and as we know, every girl loves pretty clothes, so do they. One day some of them got a huge rectangular cloth and they want to cut it into small rectangular pieces to make scarves. But different girls like different style, and they voted each style a price wrote down on a list. They have a machine which can cut one cloth into exactly two smaller rectangular pieces horizontally or vertically, and ask you to use this machine to cut the original huge cloth into pieces appeared in the list. Girls wish to get the highest profit from the small pieces after cutting, so you need to find out a best cutting strategy. You are free to make as many scarves of a given style as you wish, or none if desired. Of course, the girls do not require you to use all the cloth.

输入:

The first line of input consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers N, X, Y, N indicating there are N kinds of rectangular that you can cut in and made to scarves; X, Y indicating the dimension of the original cloth. The next N lines, each line consists of two integers, xi, yi, ci, indicating the dimension and the price of the ith rectangular piece cloth you can cut in.

输出:

The first line of input consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers N, X, Y, N indicating there are N kinds of rectangular that you can cut in and made to scarves; X, Y indicating the dimension of the original cloth. The next N lines, each line consists of two integers, xi, yi, ci, indicating the dimension and the price of the ith rectangular piece cloth you can cut in.

样例输入:

1
2 4 4
2 2 2
3 3 9

样例输出:

9

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3127

题目大意:一个大矩形,要你分割成小矩形(只能水平和竖直切割),每个小矩形都有一个价值,问如何分割能得到最大总价值。

 

解题思路:

完全背包思想,枚举所有可能情况。

对于枚举每个小矩形都可以横放竖放两种情况。

对于每种情况都有两种切割方式:横向切割或者竖向切割。

 

#include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 
 const int maxn=1024;
 int dp[maxn][maxn];
 
 struct node
 {
     int  x, y, val;
 }f[maxn];
 
 int main()
 {
     int  T, n, X, Y;
     cin >> T;
     while(T--)
     {
         cin >> n >>X >> Y;
         for(int i=0; i<n; i++)
             scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].val);
         memset(dp,0,sizeof(dp));
         for(int i=0; i<=X; i++)
             for(int j=0; j<=Y; j++)
                for(int k=0; k<n; k++)
                {
                    if(i-f[k].x>=0&&j-f[k].y>=0)
                        dp[i][j]=max(dp[i][j],max(dp[i-f[k].x][j]+dp[f[k].x][j-f[k].y],dp[i-f[k].x][f[k].y]+dp[i][j-f[k].y])+f[k].val);
                    if(i-f[k].y>=0&&j-f[k].x>=0)
                          dp[i][j]=max(dp[i][j],max(dp[i-f[k].y][j]+dp[f[k].y][j-f[k].x],dp[i-f[k].y][f[k].x]+dp[i][j-f[k].x])+f[k].val);
                }
         cout << dp[X][Y] << endl;
     }
     return 0;
 }

 

 

 

 

参考:http://www.cnblogs.com/kane0526/archive/2012/11/04/2754075.html


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。