首页 > ACM题库 > HDU-杭电 > HDU 3213-Dual Processing Task[解题报告]HOJ
2014
03-06

HDU 3213-Dual Processing Task[解题报告]HOJ

Dual Processing Task

问题描述 :

N items are to be processed with two product lines. YY operates the first line, and LMY operates the second. YY can use X processing modes for the first product
line, with his ith mode, processing an item costs Ai units of material while the item’s value increases by Pi units. Similarly LMY can use Y modes for the second
product line, with her ith mode processing an item will cost Bi units of material and get Qi units of value increment. All items must be processed in both of the
product lines, each with one of their modes, to satisfy both YY and LMY. Note that when processing an item with some mode of a product line, the cost and value
increment are totally irrelevant to the mode chosen in the other line. YY and LMY want the value increment of the items to be maximized, but there are only M
units of material available. So they have to choose their modes carefully, use no more than M units of material and still make the value increment as large as possible.

输入:

The input file contains several test cases.

The first line of each test case contains two integers N and M indicating the number of items to be processed and the quantity of material available. The next line
contains an integer X, the number of modes YY has. X lines follow, the ith line of which contains two integers Ai and Pi, the material utilized and the value
increased by YY’s ith mode of the first product line. The next line contains an integer Y, the number of modes LMY has. Y lines follow, the ith line of which contains
two integers Bi and Qi, the material utilized and the value increased by LMY’s ith mode of the second product line.

All integers except N are less than or equal to 800 and non-negative, while X and Y are always positive. N is a non-negetive integer no more than 100000.
A line with N=M=0 indicates the end of input, and should not be processed.

输出:

The input file contains several test cases.

The first line of each test case contains two integers N and M indicating the number of items to be processed and the quantity of material available. The next line
contains an integer X, the number of modes YY has. X lines follow, the ith line of which contains two integers Ai and Pi, the material utilized and the value
increased by YY’s ith mode of the first product line. The next line contains an integer Y, the number of modes LMY has. Y lines follow, the ith line of which contains
two integers Bi and Qi, the material utilized and the value increased by LMY’s ith mode of the second product line.

All integers except N are less than or equal to 800 and non-negative, while X and Y are always positive. N is a non-negetive integer no more than 100000.
A line with N=M=0 indicates the end of input, and should not be processed.

样例输入:

3 100
1
1 1
1
2 2
0 0

样例输出:

9
Hint
In the sample, both YY and LMY have only one mode to choose, with sufficient materials. Processing 1 item with the only modes of the lines causes an increment of 3 units, so the output is 9.

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

using namespace std;
const int N=1000;
int a1[N],p1[N],a2[N],p2[N],res[N],a[N],b[N];
int m;

void dp(int k)
{
 int i,j;
 memset(res,-1,sizeof(res));
 res[0]=0;
 while (k>0)
 {
 if (k&1)
 {
 for (i=0; i<=m; i++) b[i]=res[i];
 memset(res,-1,sizeof(res));
 for (i=0; i<=m; i++)
 for (j=0; j<=i; j++)
 if (b[j]>-1 && a[i-j]>-1)
 res[i]=max(res[i],b[j]+a[i-j]);
 }
 for (i=0; i<=m; i++) b[i]=a[i];
 memset(a,-1,sizeof(a));
 for (i=0; i<=m; i++)
 for (j=0; j<=i/2; j++)
 if (b[j]>-1 && b[i-j]>-1)
 a[i]=max(a[i],b[j]+b[i-j]);
 k>>=1;
 //for (i=0; i<=m; i++) if (res[i]>-1) cout<<i<<' '<<res[i]<<endl;
 }
}

int main()
{
 int n,n1,n2,i,j,ans;
 while (scanf("%d%d",&n,&m)==2)
 {
 if (n==0 && m==0) break;
 scanf("%d",&n1);
 for (i=1; i<=n1; i++) scanf("%d%d",&a1[i],&p1[i]);
 scanf("%d",&n2);
 for (i=1; i<=n2; i++) scanf("%d%d",&a2[i],&p2[i]);
 memset(a,-1,sizeof(a));
 for (i=1; i<=n1; i++)
 for (j=1; j<=n2; j++)
 if (a1[i]+a2[j]<=m)
 a[a1[i]+a2[j]]=max(a[a1[i]+a2[j]],p1[i]+p2[j]);
 //for (i=0; i<=m; i++) if (a[i]!=-1) cout<<i<<' '<<a[i]<<endl;
 dp(n);
 ans=0;
 for (i=0; i<=m; i++) ans=max(ans,res[i]);
 printf("%d\n",ans);
 }
}

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

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  3. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])