动态规划的一道题,求大神赐教

描述
看,Alice和Bob又在玩游戏了。
游戏规则如下:
Alice在纸上写出N个整数a,Bob写出一个整数S。他们轮流从这N个数中取任意个,使得这些数的和等于S。Alice先取。轮到某个人不能取时,这个人就输了。问最后的获胜者是谁。注意:两个人不能有相同取法。
输入
首先输入一个整数T,表示有T组测试数据(T≤100)。
每组测试数据包含两行。第一行包含2个整数N(1≤N≤2000)和S(0≤S≤5000);第二行包含N个整数a(0<a≤100)。
输出
按照样例输出最后的获胜者。
样例输入
2
7 10
1 2 3 4 5 5 10
5 3
1 1 1 1 1
样例输出
Case 1:Alice
Case 2:Bob

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
怎样实现在一个页面中,给两张表添加信息,求大神赐教!
怎样实现在一个页面中,给两张表添加信息,客户信息是单独一张表,附件是单独一张表求大神赐教!
《github一天一道算法题》:动态规划法解决最长公共子序列(LCS)问题的最简单方法
/* * copyleft@hustyangju * 问题:longest common subsequece problem * 思路:从底往上,利用动态规划,划分子问题,利用LCS子问题的长度变化,求得LCS * 时间复杂度O(m*n) * 空间复杂度O(m*n) */ #include #include using namespace std; class lcs { p
动态规划——如何分析一道动态规划的题
动态规划与其他的算法不一样,动态规划是没有一个固定的模板的,它只是一种思想,并不是一种特殊算法。 那么,动态规划既然没有一个固定的模板,那怎么来分析它呢?或者说,做出来了怎么写题解呢?这里给大家介绍一种分析动态规划的方法: 1:写出DP状态的表达。也就是f[XX]等于XX。 2:写出DP的转移方程。也就是f[XX] = min(f[XX],f[XX]) 3:写出状态的数
acm The Triangle
是一道动态规划的基础题。
钉子和小球(acm 1189)
pku 一道动态规划的经典题
PKU_1160 Post Office
一道非常金典动态规划题
一道关于动态归划的算法题
【说某明餐】厅供应各种标准的营养套餐。假,设将菜解单答上填共入有答题纸的对应栏内。 n项食物m1,m2,…,mn食物,每项mi的营养价值为vi,价格为pi,其中i=1,2,…,n人常需要一个算法来求解总不超过,套餐中每项食物至多出现一次。客人常需要一个算法来求解总低格不超过M的营养最大的套餐。 伪代码中的主要变量说明如下: n: 总的食物项数; v: 营养价值数组,下标从1到n,对应第1到第n项食物的营养价值; p: 价格数组,下标从1到n,对应第1到第n项食物的价格; M:总价格标准,即套餐的价格不超过M; x: 解向量(数组),下标从1到n,其元素值为0或1,其中元素值为0表示对应的食物不出现在套餐中,元素值为1表示对应的食物出现在套餐中; nv:n+1行M+1列的二维数组,其中行和列的下标均从0开始,nv[i][j]表示由前i项食物组合且价格不超过 j 的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。
LibreOJ #6165. 一道水题
题目描述 一天,szb 在上学的路上遇到了灰太狼。 灰太狼:帮我们做出这道题就放了你。 szb:什么题? 灰太狼:求一个能被 [1,n]内所有数整除的最小数字,并对 100000007 取模。 szb:这题太水了,就让我小弟来做好了。 然后你就光荣的接受了这个任务。 输入格式 一行一个数 nnn。 输出格式 一行一个数 ans。 样例 样例输入 10 样例输出 2520
动态规划经典例题
关于动态规划的介绍很多,本文希望通过重复几个最经典的例题来理解动态规划。 问题1 求一个字符串中的最长的回文子串 回文是指正着读和倒着读,结果一样,比如abcba或abba。 分析: 令状态方程p[i][j]=0表示起始位置为i,结束位置为j的字符串不为回文, p[i][j]=1,表示此回文。 状态转移方程为 p[i][j]= { p[i][j]=1;//若p[i+1][j-1]=
CSUOJ 1945 最简单的题目 背包问题
Description 小明有一台笔记本电脑,一台台式机电脑,两台电脑的性能相同,现在小明手里有N个等待运行的程序,每个程序运行所需的时间分别为n1,n2,n3,n4……,一台电脑同一时刻只能运行一个程序,一个程序只需要运行一次。两台电脑同时开始运行,请问小明该如何分配程序在这两台电脑上运行,使得最后结束运行的电脑的运行时间最短。 Input 输入不超过30组数据,每组数
每天一道算法题(30)——高效的求斐波拉契数列
对于斐波拉契经典问题,我们都非常熟悉,通过递推公式F(n) = F(n - 1) + F(n - 2),我们可以在线性时间内求出第n项F(n),现在考虑斐波拉契的加强版,我们要求的项数n的范围为int范围内的非负整数,请设计一个高效算法,计算第n项F(n)。第一个斐波拉契数为F(0) = 1。给定一个非负整数,请返回斐波拉契数列的第n项,为了防止溢出,请将结果Mod 1000000007。
Leetcode198.+算法期中1005. 动态规划问题之最大最小和问题
动态规划 最大最小和
ubuntu 乱码 求大神赐教
windows下的东东在ubuntu下打开以后乱码,百度之后解决方案是: 1.打开终端,在其中输入命令: gconf-editor 并回车。 2. 在新开的窗口里,在左边依次展开“apps”、“gedit-2”、“preferences”、“encodings”。 3. 在右边的窗口里,双击“auto_detected”。 4. 在弹出的对话框里,单
OJ.3158: 这还是一道简单题
3158: 这还是一道简单题 时间限制: 1 Sec  内存限制: 128 MB 提交: 27  解决: 11 [提交][状态][讨论版] 题目描述 一个 N*N 矩阵中有不同的正整数,经过这个格子,就能获得相应价值的奖励,从左上走到右下,只能向下向右走,求能够获得的最大价值。 例如:3 * 3 的方格。     1 3 3     2 1 3     2 2 1
fzu 1698解题报告
求最大乘积 的源代码 次题是fzu 4月月赛题 是一道数学题啊
又一道简单题
又一道简单题 Time Limit: 5000MS Memory Limit: 65535KB 64bit IO Format: SubmitStatusDescription 输入一个四个数字组成的整数 n,你的任务是数一数有多少种方法,恰好修改一个数字,把它 变成一个完全平方数(不能把首位修改成 0)。比如 n=7844,有两种方法:3844=62^2和 7744=8
一道“求阴影面积”初等几何题的“凑面积、做加减”解法
一道“求阴影面积”初等几何题的“凑面积、做加减”解法这个老外真耐心, 我连他的图都不想再画一遍; 通常是辅助线正余弦定理之类的搞定; 然而用到海伦公式之类的,难说:原始链接说他复杂是因为,辅助线可以更简单: 写后感 感觉由StackEdit修改而来的CSDN-Markdown编辑器不太好用;太希望集成更多更强的东西了,反而抓不住重点。解决以下问题才是关键啊:1.数学公式; 2.程序代码;其它的
习题 2.4(4) 求1+2+3+···+100。
C程序设计 (第三版) 谭浩强 习题2.4(4) 个人设计习题 2.4(4) 求1+2+3+···+100。代码块方法1:#include <stdio.h>main() { int i, t; for (i = 1, t = 0; i <= 100; i++) t = t + i; printf("%d\n", t); return 0; }方法2:#
动态规划求最短编辑距离.rar
动态规划求最短编辑距离.rar 动态规划求最短编辑距离.rar 动态规划求最短编辑距离.rar 动态规划求最短编辑距离.rar 动态规划求最短编辑距离.rar 动态规划求最短编辑距离.rar 动态规划求最短编辑距离.rar
滴滴出行2017秋招笔试真题-编程题汇总 - 题解
滴滴出行2017秋招笔试真题-编程题汇总 - 题解 滴滴的题考经典算法比较多啊,两道经典动态规划,一道经典搜索题,一道编程之美原题(听别人说是编程之美上的,自己并不清楚),两道水题.
【BZOJ2759】一道动态树的好题
2759: 一个动态树好题Time Limit: 10 Sec Memory Limit: 128 MB Description有N个未知数x[1..n]和N个等式组成的同余方程组: x[i]=k[i]*x[p[i]]+b[i] mod 10007 其中,k[i],b[i],x[i]∈[0,10007)∩Z 你要应付Q个事务,每个是两种情况之一: 一.询问当前x[a]的解 A a 无
OJ.3157: 这是一道简单题
3157: 这是一道简单题 Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 139  Solved: 10 [Submit][Status][Web Board] Description 为了准备即将到来的考试,小欣每天都在努力练习。 考试开始了,总共有 n 道题目。 对于第 i 道题,小欣可以在 ti 分钟内做出来
csu 1785: 又一道简单题 (没错,简单题)
链接:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1785 Description 输入一个四个数字组成的整数 n,你的任务是数一数有多少种方法,恰好修改一个数字,把它 变成一个完全平方数(不能把首位修改成 0)。比如 n=7844,有两种方法:3844=62^2和 7744=88^2。 Input
最大乘积--动态规划
【题目描述】 今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先 生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活 动,你的一个好朋友XZ也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样 一道题目:  设有一个长度N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。 
C语言 每天做一道编程题
好久没做编程题了,算法和数据结构该忘的也都忘干净了,今天开始至少每天做道题,然后写写tips吧,各种都可以。 3.13 写了两道简单的PAT:3n+1(卡拉兹猜想)和将数字转换成拼音       主要是体会一下输入字符串的三种方式:       scanf("%s",s);//s是数组名,或者是指针。       gets(s);//可以包括空格,而scanf不可以包括空格      
用微信 远程遥控 服务器
摘要 环境搭建 开启配置 服务器环境 核心类 验证 回复 拓展 添加机器人 命令模式 完整代码 总结摘要微信公众好的开发很火,小程序更火。于是也凑个热闹,尝试了一把。大致的功能还是有的,不过是不全,很多地方我没有进行处理。不过对于纯文本方式的交流,已经没有问题啦。 环境搭建下面大致的讲讲微信公众号的原理吧。可能我理解的有些不到位,如果有些许不当,欢迎批评指教。 客户端发送给微信平台请求,微信平
每日一道算法题——1
求字符串字串的长度。
每天一道编程题(1)
现在有一张半径为r的圆桌,其中心位于(x,y),现在他想把圆桌的中心移到(x1,y1)。每次移动一步,都必须在圆桌边缘固定一个点然后将圆桌绕这个点旋转。问最少需要移动几步。 输入描述: 一行五个整数r,x,y,x1,y1(1≤r≤100000,-100000≤x,y,x1,y1≤100000) 输出描述: 输出一个整数,表示答案 输入例子: 2 0 0 0 4 输
今天在刷题的过程看到一位大神写的代码
题目描述 对字符串中的所有单词进行倒排。 说明: 1、每个单词是以26个大写或小写英文字母构成; 2、非构成单词的字符均视为单词间隔符; 3、要求倒排后的单词间隔符以一个空格表示;如果原字符串中相邻单词间有多个间隔符时,倒排转换后也只允许出现一个空格间隔符; 4、每个单词最长20个字母;输入描述: 输入一行以空格来分隔的句子输出描述: 输出句子的逆序输入例子: I am a stu
IP地址分类编址
1 IP地址的用途、分类及表示方法IP用途 标记某个主机所在的位置 种类 分类编址:早期设计,存在缺陷 无分类编址:用来代替分类编址 IP地址的表示方法 二进制记法(1000 0001 0000 1011 0000 1011 1110 1111) 点分十进制记法(可读性高)(129.11.11.239) 十六进制记法(注册表、编程使用)(0x810B0BEF) 2 IP地址分类编址
qduoj 96 一道非常简单的签到题
一道非常简单的签到题 发布时间: 2016年7月2日 20:32   最后更新: 2016年7月2日 21:48   时间限制: 1000ms   内存限制: 128M 描述 给你k,a,b三个数,问[a,b]区间内有多少个数可以整除k。(n / k == 0) 输入 多组输入,即输入包括多行,每行三个数k,a,b。 其中1 ≤ k ≤ 10^18,-
《github一天一道算法题》:搜索二叉树接口实现大合集
读书、思考、写代码! 说明: (1)这里实现了搜索二叉树的全部常用操作 (2)限于时间和精力,实现的较为粗糙,内存泄露、成员变量访问控制、返回类型、异常安全等没有照顾的到 (3)一切实现的手段都是贴近底层操作,关注原理。以后可能对推倒重来,实现一个完备的接口系统。 /********************************************* * copyright@hus
动态规划最长递增子序列
动态规划最长递增子序列 已经实现 请大家赐教
表单发布不成功!这个问题估计不会常见,但真的碰到了真的就困扰了
这几天在设计新表单的时候,有个表单在上载时出现了问题“操作无法完成”,很是纳闷,怎么可能, 前一分钟在上载其他表单的时候是没有问题,偏偏倒着这张表单就出问题 了,所以我在MOSS群里请教了这个问题,他们是说表单的安全与信任没有设置对,而我所有的表单设置都是一样的,想想真见鬼~刚好也到下班的时间了,一个群友说他也碰到过这样的问题,他的解决方案是等它自己会好的~所以反正也要下班了 ,所以 我就开始等
C语言版flappy bird
大神的C语言版flappy bird,可以随意修改,欢迎赐教讨论
CSU 1785 NBUT 1647 又一道简单题
因为范围比较小,所以直接枚举就可以判断是不是完全平方数。 而且这样的话,可以忽略掉首位不能变成0这个限制了,代码就变得更有对称美。
bzoj3505(排列组合)
一直对排列组合有点头疼,总是有情况没有考虑到 考虑补集,先把答案赋为c(n*m)(3),然后减去三点共线的情况。 首先三点在一条水平或竖直的直线上非常好处理。直接减去c(n)(3)*m+c(m)(3)*n即可。 然后考虑不斜着的情况。 我们枚举一下边上两个点的横纵坐标之差(i,j)。那么中间的点可选的位置就是gcd(i,j)-1;然后再乘上这种直线的条数即可。注意要先处
一道初等平面几何竞赛题的暴力解法
问题一道初中数学竞赛,平面几何题计算: 这里改成了证明题,反正思路是一样的。暴力解法暴力破解的方法是怎样的?首先,代数方法对很大一部分这类问题都是可以算的。但是应该注意下面几点: 1. 并不是所有几何问题都很容易代数化的; 2. 直接代数化并不总能保证所用代数方法不超出初等数学范畴; 3. 代数化之后的代数求解方法也不总能简化求解的繁琐程度。对这个问题,先建立如下图的坐标系: 可以容易(计
[TYVJ 1927] 『Citric II』一道防AK好题 · 模拟
出题人真是丧(gan)心(de)病(piao)狂(liang)! 题面说的各种玄乎各种牛逼然而却毫无卵用 对于最后一组a b c ,因为要加上lastans以后=0,所以明显倒数第二组的解就是ans=-a 然后我们把这个ans代入上一组数据的表达式,就可以得到一个关于上上组数据的解,然后不断向前推,结果就出来了。 就出来了。 出来了。 来了。 了。 。 简直丧心病狂 #incl
【面试编程题】6-动态规划类题
下面的例题来自剑指offer,都是使用动态规划代替递归避免重复求解的例子。1.斐波那契数列题目描述 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。 n<=39 思路:斐波拉数列f(n)=f(n-1)+f(n-2);如果使用递归,会造成很多重复求解,所以使用使用动态规划,斐波拉数列是非常典型的使用动态规划求解的例子。public class Solution {
相关热词 c#多人合作开发项目策略 c# cad 坐标转换 c# 窗口内运行word c#线程睡眠 c# 静默打开打印机 c#获取当前路径的上一级 c# 去除线条 c# 取整倍数 c#窗体最大化控件不变 c# 程序更新程序案例