有一个m*n的矩阵,每个位置都有一个武力超强的武士,而你也已经山中修炼了30年。现在你要挑战这些武士。挑战的规则和顺序是这样的:第一个和最后一个你要挑战的分别是位于左上角和右上角的武士,而每挑战完一个你可以选择相邻的右边、上边或下边的武士继续挑战,但是挑战过的就不能再选择了。刚开始你的血值是0,每打完一个武士,你的血值的变化等于相应位置上的整数(正数代表增血,负数代表掉血)。当然,你不会因为血值小于0而死掉。为了到最后得到更大的血值,你该如何根据规则来选择挑战的武士呢?
输入:输入有多组测试数据(不超过100组)。每组数据的第一行输入两个正整数m,n(m<=100,n<=100)。接下来的m行,每行n个整数,分别代表挑战相应位置武士你的血值的变化,每个整数都大于等于-100且小于等于100。
输出:每组测试数据输出一行,输出一个整数,代表根据最优的打法,你打完右上角那个武士时能获得的最大的血值。
输入样例:
3
1
2
3
2
1
1
输出样例:
18
4
解法:
DP或者记忆化搜索。每个点会有两个状态。Dp[i][j][0]表示向右或向下走的最大值,Dp[i][j][1]表示向右或向上的最大值。根据题意得到的转移方程是:Dp[i][j][0]=num[i][j]+max(Dp[i+1][j][0],max(Dp[i][j+1][1],Dp[i][j+1][0]);
Dp[i][j][1]=num[i][j]+max(Dp[i+1][j][1],max(Dp[i][j+1][1],Dp[i][j+1][0]);
输入:输入有多组测试数据(不超过20组),每组数据第一行有两个正整数n(n<=1000),T(T<=1000000),接下来n行的每一行都有三个整数,分别代表第i只蚂蚁的Ai,Bi,Ci。输入保证每个位置最多有一只蚂蚁。
输出:对于每组测试数据,将在T时间内n只蚂蚁两两相遇的次数输出在一行。
输入样例:
2
1
-1
输出样例:
解法:
解法:
严格的计算需要概率论的一些知识。大概方向的就是积分暴力求解通项公式。公式是:结果=
n只蚂蚁从多维空间回来以后都感觉晕乎乎的,大家准备排成一排报个数。由于头晕,大家报的数有点乱,但是每个蚂蚁都仍清醒地知道自己报的数要大于等于前一个蚂蚁报的数并都遵守了这个规则。在遵守这个规则的前提下,每个蚂蚁可以从[1,m]m个正整数之内任意挑选一个来报。第一个蚂蚁就1-m任意报了。
请问,根据上述情况,n只蚂蚁共有多少种不同的合法报数序列呢。
输入:输入有多测试组数据(不超过30组),每组数据占一行,有两个正整数n,m(n,m<=100000)。
输出:将每组测试数据结果对100000007取模输出,每组答案占一行。
输入样例:
2
1
输出样例:
1
2
解法:
这道题本来给的数据是10000,后来缩小到了100,为的是让用DP的过。但是由于本人的失误,在给姜老师的文档里忘记改了,还请大家见谅。
输入:输入有多组测试数据(不超过2000组)。每组数据占一行,有5个整数x,y,T,a,b。(-10000<=x,y,a,b<=10000,0)
输出:每组测试数据的答案输出各一行,答案四舍五入到小数点后第4位即可。
输入样例:
2
3
输出样例:
2.9517
解法:
举例一种情况如图。求时间即求出EF弧的角度即可。圆心角等于圆心角的一半,即在三角形AEF中求出角EAF即可。在三角形AEF中,我们可以直接算出来角AEB(圆心角AOB的一半)、角BEF(等于角FAB),角AFE(等于角ABE)。即利用三角形内角和等于π算出角EAF。还有一种情况就是当D在AB的另一边的时候,类似于上述解法也可推出。(注:此题数据设有trick,即当点D在线段AB上的时候,答案直接是T,当D位于圆之外的时候直接输出0)。
输入:输入有多组测试数据(不超过1000组),每组数据只有一个二进制数并且占一行,每个二进制数长度不超过30。
输出:每组数据按照样例格式输出一行。
输入样例:
101
1000
输出样例:
1110*111=1100010
101*101=11001
1000*1=1000
解法:全场最水一题,由于长度不超过30,所以long
输出:每组测试数据输出一个整数,表示另一本书至少要多少页。
输入样例:
输出样例:
2
即两本书为了产生最大的摩擦力,一定是页数较少的一本书B与另一本较厚书A每页交叉,并B最后一页位于A最后一页的上面。