misschuer

常用链接

统计

积分与排名

百事通

最新评论

HDU 1711

1358317 2009-05-11 19:15:41 Accepted 1171 1125MS 524K 783 B C++ 此最相思
#include <iostream>
using namespace std;

#define MAX 51

int dp[ 250001 ];

int main()
{
  
int v[ MAX ] , bb[ MAX ];
  
int i , j , k , n , kk;
  
while (cin >> n && n > 0)
  
{
    
int sum = 0;
    
for (i = 1 ; i <= n ; ++ i)
    
{
        cin 
>> v[ i ] >> bb[ i ];
        sum 
+= v[ i ] * bb[ i ];
    }

    
int t = sum;
    sum 
/= 2;
    
for (i = 0 ; i <= sum ; ++ i)
         dp[ i ] 
= 0;
    dp[ 
0 ] = 1;
    
for (i = 1 ; i <= bb[ 1 ] ; ++ i)
        dp[v[ 
1 ] * i] = 1;

    
for (i = 2 ; i <= n ; ++ i)
      
for (j = 0 ; j <= sum ; ++ j)
        
for (k = 0, kk = 0; k + j <= sum && kk <= bb[ i ] ; k += v[ i ] , ++ kk)
               
if (dp[ j ] == 1)
                   dp[j 
+ k] = 1;

        
for (i = sum ; i >= 0 ; -- i)
            
if (dp[ i ])
                
break;
    cout 
<< t - i << " " << i << endl;
  }

  
return 0;
}

posted on 2009-05-11 19:16 此最相思 阅读(168) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理