misschuer

常用链接

统计

积分与排名

百事通

最新评论

HDU 1709

//1358214 2009-05-11 18:38:31 Accepted 1709 156MS 424K 992 B C++ 此最相思 
#include <iostream>
using namespace std;
#define MAX 10001

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


    dp[ 0 ] = 1;

    for (i = 1 ; i <= n ; ++ i)
    {
        for (j = 0 ; j <= sum ; ++ j)
        {
          bb[j] += dp[j];
          if(tt[i] + j <=sum)
              bb[tt[ i ] + j] += dp[ j ];
          temp = tt[ i ] - j;
          if (temp < 0)
              temp = -temp;
          bb[temp] += dp[ j ];
        }
        for (j = 0 ; j <= sum ; ++ j)
        {
          dp[ j ] = bb[ j ];
          bb[ j ] = 0;
        }
    }

        for (i = 1 ; i <= sum ; ++ i)
            if (!dp[ i ])
            {
                kk[++ k] = i;
            }
            cout << k << endl;
            for (i = 1 ; i <= k ; ++ i)
            {
                if (i != 1)
                    cout << " ";
                cout << kk[ i ];
            }
            if(k)
            cout << endl;
  }
  return 0;
}

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


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