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