773
技术社区[云栖]
HDU1171 DP
这题老师上课说用母函数做 想了一会 还是DP吧 开了个DP标记数组 求完各个组合的值就行了
力求代码简洁= = 向学长学习
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
bool dp[3000000];
int main()
{
int value,n,num,sum,a;
while(~scanf("%d",&n)&&(n>=0))
{
memset(dp,0,sizeof(dp));
dp[0]=1;
sum=0;
for(int i=0; i<n; i++)
{
scanf("%d%d",&value,&num);
sum+=value*num;
dp[value]=1;
for(int j=1; j<num; j++)
for(int k=0; k<=sum; k++)
if(dp[k])
dp[k+value]=1;
}
for(a=sum/2; a>=0; a--)
if(dp[a])
break;
printf("%d %d\n",sum-a,a);
}
return 0;
}
最后更新：2017-04-04 07:03:18