HDU 找单词

zz/2024/2/26 0:27:56

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

Source

2006/1/15 ACM程序设计期末考试

题目大意:每个单词都有一个值,从A、B…到Z的值分别为1、2…到26

现在给你26个字母每个字母的个数,问:能找到多少个字母总价值<=50

的单词数。(单词排列顺序无关,ACM和CMA和AMC都视为同一个单词)

思路:很多人都是用母函数做的,这里说下动态规划的思想。

把A、B…到Z看做26种物品,每种物品的价值为1、2…到26,每种物品的

个数有num[i]个。现有一个容量为50的背包,问有多少种装法,能满足背

包中总价值<=50

过程:开个二维数组,一维26个表示字母种类,二维50个表示价值。最后

从1-50种统计个数。这里0个字母不是单词。

注意:初始化的时候dp[0][0] = 1。

因为我们初始化是未放物品时符合条件的最优解。

0个字母0容量的时候方案数为1

同理容量为0的时候,无论存在哪个字母,方案数都为0,因为状态转移方

程 dp[i][j] += dp[i-1][j-w[i]*k] 是递推的,每种字母方案数都是由上一种

字母得到的,所以不需要每种字母都初始化。

当然,也可以这样初始化:

  1. for (i = 0; i <= 26; i++)
  2. dp[i][0] = 1;
最终代码:

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. using namespace std;
  5. int w[30],num[30],dp[55][55];
  6. int main()
  7. {
  8. int N;
  9. scanf("%d",&N);
  10. while(N--)
  11. {
  12. memset(w,0,sizeof(w));
  13. memset(dp,0,sizeof(dp));
  14. for(int i = 1; i <= 26; i++)
  15. {
  16. w[i] = i;
  17. scanf("%d",&num[i]);
  18. }
  19. dp[0][0] = 1;//0个字母,0容量的时候方案数为1
  20. // for (i = 0; i <= 26; i++)
  21. // dp[i][0] = 1;
  22. for(int i = 1; i <= 26; i++)//有N种物品
  23. {
  24. for(int j = 0; j <= 50; j++)//容量
  25. {
  26. for(int k = 0; k <= num[i] && w[i]*k <= j; k++)//物品数量
  27. dp[i][j] += dp[i-1][j-w[i]*k];//最优方案个数
  28. }
  29. }
  30. int ans = 0;
  31. for(int i = 1; i <= 50; i++)
  32. ans += dp[26][i];
  33. printf("%d\n",ans);
  34. }
  35. return 0;
  36. }






http://www.ngui.cc/zz/2641759.html

相关文章

先验概率、后验概率、极大似然估计

先验概率 先验概率&#xff08;prior probability&#xff09;是指根据以往经验和分析得到的概率。例如投硬币事件&#xff0c;我们在执行这个事件之前就已经了解其符合二项分布&#xff0c;然后直接根据二项分布分析出的概率被称作是先验概率。它往往作为"由因求果"…

Python 网页爬虫

import re #匹配的库 import requests headers {Cookie:UM_distinctid16828a999356ee-01dbffc4bd71a8-33504275-144000-16828a99936840; CNZZDATA12553571271573548009-1546867979-%7C1546921578,Host:m.网站名称.com,User-Agent:Mozilla/5.0 (Windows NT 10.0; WOW64) Apple…

将文件数据读入结构体

将文件数据读入结构体 #include <stdio.h> #include <string.h> #include <stdlib.h> struct infostu {char no[20]; //学号 char name[20]; char sex[4];int age;char major[20]; //专业班级 }; int main() {int i0,j;struct infostu student[5…

CNN——卷积、池化与误差反向传播

卷积神经网络&#xff08;CNN&#xff09; 组成&#xff1a;输入层、卷积层、激活函数、池化层、全连接层 卷积神经网络中重要概念就&#xff1a; 深度&#xff1a;深度大小就等于所用的filter的个数[卷积层]&#xff0c;也可以理解为提取的层数。 权值共享&#xff1a;给一张…

iOS H5交互 -MUI

最近公司要求以后的项目要用iOS原生框架和h5页面结合完成,发现网上这方面的资料好少(js交互的资料是挺多的&#xff0c;我的h5页面是用MUI完成的&#xff0c;这方面的资料真的好少) 把我最近的进度做个总结 去MUI官网下载SDK 点击这里查看官方文档&#xff0c;下载SDK 下图是SD…

Hibernate配置异常

Orders和OrderItem配置 错误如图&#xff1a; 找了很久&#xff0c;才发现是因为和数据库对应的字段不同。 实体类&#xff1a; orders OrderItem xxx.hbm.xml 由于数据库对应的字段不存在itemid&#xff0c;所以图片上蓝色这一段代码应不要 数据库表格&#xff1a;

ssh+filter+cookie实现自动登陆

在ssh中&#xff0c;filter的web.xml没有正确配置的话&#xff0c;就会出现空指针异常&#xff0c;因为他执行的时候没有去找bean。也就是说filter和spring没有结合起来 实现用户自动登陆就是把用户信息保存在cookie里&#xff0c;当用户第二次访问的时候无需登陆。 实现自动…

hql语句中使用占位符:xx 的时候,查询所有查询查不出来

在hql语中&#xff0c;我们可以使用&#xff1f;也可以使用占位符&#xff1a;xx&#xff0c; 其中&#xff1f;可以使用query.setParameter(0,"%%"); 但是占位符使用query.setParameter("xx","%%")&#xff1b;的时候查询不出来所有的记录&am…

计算时间,指定时间的多少个月后

/*计算时间日期 */ function DateAdd(interval,number,date) { switch(interval){ case "m" : { if(date.getMonth()number>12){ date.setMonth(date.getMonth()number-12); date.s…

如何在js中判断是否包含某个字符串

var vkind$("#vkind").val(); var flag1vkind.indexOf("次卡"); //如果flag1不为-1的话&#xff0c;说明指定字符串中包含“次卡”两个字&#xff0c; if(-1!flag1){ //次卡 $("#ubksj").val(""); $("…