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 此最相思 阅读(236) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理