ACM___________________________

______________白白の屋
posts - 182, comments - 102, trackbacks - 0, articles - 0

导航

公告

Locations of visitors to this page
<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(24)

随笔分类(332)

随笔档案(182)

FRIENDS

搜索

  •  

积分与排名

  • 积分 - 216310
  • 排名 - 115

最新随笔

最新评论

阅读排行榜

评论排行榜

HDOJ HDU 2082 找单词 ACM 2082 IN HDU

Posted on 2010-08-07 21:00 MiYu 阅读(1471) 评论(0)  编辑 收藏 引用 所属分类: ACM ( 母函数 )ACM ( 水题 )
MiYu原创, 转帖请注明 : 转载自 ______________白白の屋

题目地址:
         http://acm.hdu.edu.cn/showproblem.php?pid=2082
题目描述:
Problem Description
假设有x1个字母A, x2个字母B,.. x26个字母Z,同时假设字母A的价值为1,字母B的价值为2,.. 字母Z的价值为26。那么,对于给定的字母,可以找到多少价值
<=50的单词呢?单词的价值就是组成一个单词的所有字母的价值之和,比如,单词ACM的价值是1+3+14=18,单词HDU的价值是8+4+21=33。(组成的单词与排列顺序无关,比如ACM与CMA认为是同一个单词)。
 

Input
输入首先是一个整数N,代表测试实例的个数。
然后包括N行数据,每行包括26个
<=20的整数x1,x2,..x26.
 

Output
对于每个测试实例,请输出能找到的总价值
<=50的单词数,每个实例的输出占一行。
 

Sample Input
2
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9
 

Sample Output
7
379297

题目分析:
         有是一个很标准的母函数的题目 ( 更多母函数的了解 请看 <<母函数详解>>  ).   不过此题可以进行适当的优化, 因为数据是 26个数据顺序输入的,不是稀疏多项式,所以直接用一个变量输入就行了.

代码如下:
MiYu原创, 转帖请注明 : 转载自 ______________白白の屋

#include 
<iostream>
using namespace std;
int num1[51];
int num2[51];
int main ()
{
    
int T;
    
while ( cin >> T )
    {
           
while ( T -- )
           {
                   memset ( num1, 
0 , sizeof ( num1 ) );
                   memset ( num2, 
0 , sizeof ( num2 ) );
                   num1[
0= 1;
                   
for ( int i = 1; i <= 26++ i )
                   {
                         
int cnt ;
                         cin 
>> cnt;
                         
if ( cnt == 0 )
                         {
                              
continue
                         }
                         
for ( int j = 0; j <= 50 ; ++ j )
                         {
                               
for ( int k = 0; k <= cnt && k * i + j <= 50;  k ++ ) 
                               {
                                     num2[ k 
* i + j ] += num1[j]; 
                               }
                         } 
                         
for ( int j = 0; j <= 50++ j )
                         {
                               num1[j] 
= num2[j];
                               num2[j] 
= 0
                         }
                   } 
                   
int total = 0
                   
for ( int i = 1; i <= 50++ i )
                   {
                         total 
+= num1[i]; 
                   }
                   cout 
<< total << endl;
           } 
    }
    
return 0


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