注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

HDU 1171 Big Event in HDU  

2014-04-21 16:12:01|  分类: 母函数 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Time Limit : 10000/5000ms (Java/Other)   Memory Limit : 65536/32768K
(Java/Other)

Total Submission(s) : 29   Accepted Submission(s) : 10

Problem Description

Nowadays, we all know that Computer College is the
biggest department in HDU. But, maybe you don't know that Computer College had
ever been split into Computer College and Software College in 2002. The
splitting is absolutely a big event in HDU! At the same time, it is a trouble
thing too. All facilities must go halves. First, all facilities are assessed,
and two facilities are thought to be same if they have the same value. It is
assumed that there is N (0<1000 div="" kinds="" different="" value="" different="" facilities="" of="" kinds="" >
 


Input

Input contains multiple test cases. Each test case
starts with a number N (0 < N <= 50 -- the total number of different
facilities). The next N lines contain an integer V (0< div of="" processed="" be="" to="" not="" is="" case="" test="" this="" and="" input="" terminates="" integer="" negative="" a="" with="" starting="" different="" are="" v="" all="" that="" assume="" can="" you="" each="" facilities="" the="" number="" --corresponding="" m>< m an="" facility="" --value="" >
 


Output

For each case, print one line containing two integers A
and B which denote the value of Computer College and Software College will get
respectively. A and B should be as equal as possible. At the same time, you
should guarantee that A is not less than B.

 


Sample Input

2
10 1
20 1
3
10 1
20 2
30 1
-1

 


Sample Output

20 10
40 40

 


Author

lcy

 


< >




  • Hangzhou Dianzi University Online Judge
  • Copyright ? 2005-2014 HDU ACM Team. All
    Rights Reserved.
<1000 >

#include<stdio.h>
#include<string.h>
int c1[200000],c2[200000];
int a[200],c[200];
int main()
{
int n,i,j,sum,k;
while(scanf("%d",&n)!=EOF)
{
if(n<0) break ;
sum=0;
for(i=1;i<=n;i++)
{
scanf("%d %d",&a[i],&c[i]);
sum+=a[i]*c[i];
}
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(i=0;i<=a[1]*c[1];i+=a[1])//
{
c1[i]=1;
}
for(i=2;i<=n;i++)
{
for(j=0;j<=sum;j++)
for(k=0;k<=a[i]*c[i]&&k+j<=sum;k+=a[i])//不是k++ 而是加a[i]
c2[k+j]+=c1[j];
for(j=0;j<=sum;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
for(i=sum/2;i>0;i--)
{
if(c1[i]!=0)
break;
}
printf("%d %d\n",sum-i,i);
}
return 0;
}

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<fstream>
using namespace std;

int a1[100000];//保存的数组;
int a2[100000];/*变化的数组*/
int b1[100],b2[100];/*输入的数据,次数*/

int main()
{
int T;
int i,j,k;
int sum;
//ifstream cin("aa.txt");
while(scanf("%d",&T)!=EOF)
{
if(T<0) break;
sum=0;
for(i=1;i<=T;i++)
{
cin>>b1[i]>>b2[i];
sum+=b1[i]*b2[i];
}
for(i=0;i<=sum;i++)
{
a1[i]=0;
a2[i]=0;
}
for(i=0;i<=b1[1]*b2[1];i+=b1[1])/*初始化我们的第一项i+=b1[1])这个特别的初始化不和我们以前的一样*/
{
a1[i]=1;
}
for(i=2;i<=T;i++)
{
for(j=0;j<=sum;j++)
for(k=0;k<=b2[i]*b1[i]&&k+j<=sum;k+=b1[i])/*第二项收到了我们的总数的限制和次数的限制*/
a2[j+k]+=a1[j];

for(j=0;j<=sum;j++)
{
a1[j]=a2[j];
a2[j]=0;
}

}
for(i=sum/2;i<=sum;i++)
{
if(a1[i]!=0)
{
i=i>sum-i?i:sum-i;
printf("%d %d\n",i,sum-i);
break;
}
}
}
return 0;
}



#include<stdio.h>

int a1[500000];//保存的数组;
int a2[500000];/*变化的数组*/
int b1[1000],b2[1000];/*输入的数据,次数*/

int main()
{
int T;
int i,j,k;
int sum;
while(scanf("%d",&T)!=EOF)
{
if(T<0) break;
sum=0;
for(i=1;i<=T;i++)
{
scanf("%d%d",&b1[i],&b2[i]);
sum+=b1[i]*b2[i];
}
for(i=0;i<=sum;i++)
{
a1[i]=0;
a2[i]=0;
}
for(i=0;i<=b1[1]*b2[1];i+=b1[1])/*初始化我们的第一项i+=b1[1])这个特别的初始化不和我们以前的一样*/
{
a1[i]=1;
}
for(i=2;i<=T;i++)
{
for(j=0;j<=sum;j++)
for(k=0;k<=b2[i]*b1[i]&&k+j<=sum;k+=b1[i])/*第二项收到了我们的总数的限制和次数的限制*/
a2[j+k]+=a1[j];

for(j=0;j<=sum;j++)
{
a1[j]=a2[j];
a2[j]=0;
}

}
for(i=sum/2;i<=sum;i++)
{
if(a1[i]!=0)
{
i=i>sum-i?i:sum-i;
printf("%d %d\n",i,sum-i);
break;
}
}
}
return 0;
}

  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017