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


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