A. Dreamoon and Stairs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Dreamoon wants to climb up a stair of n steps. He can climb 1 or 2 steps at each move. Dreamoon wants the number of moves to be a multiple of an integer m.
What is the minimal number of steps making him climb to the top of the stairs that satisfies his condition?
Input
The single line contains two space separated integers n, m (0?
Output
Print a single integer ? the minimal number of moves being a multiple of m. If there is no way he can climb satisfying condition print ?-?1 instead.
Sample test(s)
Input
10 2
Output
Input
3 5
Output
-1
Note
For the first sample, Dreamoon could climb in 6 moves with following sequence of steps: {2, 2, 2, 2, 1, 1}.
For the second sample, there are only three valid sequence of steps {2, 1}, {1, 2}, {1, 1, 1} with 2, 2, and 3 steps respectively. All these numbers are not multiples of 5.
题意：给两个数n,m，
现在要求爬楼梯，一次可以爬
一个或两个阶梯，要求爬完n个阶梯，
求爬的次数为m的倍数时，最少次数是多少，
若不存在答案输出-1。
做法：很明显尽量爬两步。
代码：
#include#include
输出0，
若有解，求出第二个串还需要多少个+，
统计？的数量，求出组合数除以所有的可能数量。
或者，直接爆搜，因为最多只有10个字符，
所以，不会超时。
代码：
#include#include
输出任意一组。
做法：
很明显，当任意集合内的所有元素除以k后，
两两元素之间是互质的，然后为了满足元素最大值最小，
在除掉k后，任意集合内肯定是由3个奇数，1个偶数组成，
因为若少一个奇数，就会有至少一对数不互质，
若多一个奇数，元素最大值就会变大。
所以，从1开始构建所有元素集合即可。
代码：
#include#include
输出n个新串的所谓最大数量。
做法：
dp[i][j]:第一个串0到i的位置除去j个字符可以得到的最大数量
（j<=i,且除去的位置不包括i）
a[i]：从i开始，包含第二个串的最近位置，若没有赋值为-1，
ns:第一个串的长度
np:第二个串的长度
有
dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
//若不删除第i个字符dp[i+1][j]=dp[i][j]
dp[i+1][j+1]=max(dp[i][j],dp[i+1][j+1]);
//若删除第i个字符dp[i+1][j+1]=dp[i][j]
if(a[i]>0)
dp[i+a[i]][j+a[i]-np]=max(dp[i][j]+1,dp[i+a[i]][j+a[i]-np]);
//若删除从i开始后到i+a[i]不包含与第二个串相同的字符，
dp[i+a[i]][j+a[i]-np]=dp[i][j]+1
因为dp[ns-1][j]木有考虑ns-1个字符是否删除的情况，
所以最终答案存在dp[ns][j]中。
代码：
#include#include
