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
#include <stdio.h>
#include <string.h>
int arr[51],tmp[51],num[27];
int main()
{
freopen("in.txt", "r", stdin);
int t,i,j,k,ans;
scanf("%d", &t);
while(t--){
for(i=1; i<=26; i++)
scanf("%d",&num[i]);
memset(tmp,0,sizeof(tmp));
memset(arr,0,sizeof(arr));
for(i=0; i<= num[1]; i++)
{
arr[i] = 1;
tmp[i] = 0;
}
for(i=2; i<=26; i++) // i就表示第i个字母,也是DP的应用
{
if(num[i] == 0 )
continue;
for(j=0; j<=50; j++)
{
for(k=0; k<= num[i] && k*i + j <= 50; k++) //k表示第j个指数。
{
tmp[k*i + j] += arr[j]; // 第i个字母的价值也为i
}
}
for(j=0; j<=50; j++)
{
arr[j] = tmp[j];
tmp[j] = 0;
}
}
ans = 0;
for(i=1; i<=50; i++)
{
ans += arr[i];
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
90%的杭电母函数解题报告,有题目加解题思路,和ac掉的代码
ACM培训好资料!能帮助你快速提高ACM AC题目的能力,值得一下
hdu 1695 GCD(欧拉函数+容斥原理).docx
acm 技术大牛 课件 HDU ...(lecture_06)母函数 (lecture_7)特殊的数 (lecture_8)组合博弈入门 (lecture_09贪心算法 (lecture_11)搜索入门 (lecture_12)二分匹配及其应用 (lecture_13)动态规划(2) 并查集
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu ACM 各种排序
HDU 动态规划(46道题目
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
这是我自己的AC代码,都是自己做的,有的很容易出错,大家看的时候要仔细点,加油
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)