首页 > 试题广场 >

逃离农场

[编程题]逃离农场
  • 热度指数:1088 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
牛牛在农场饲养了n只奶牛,依次编号为0到n-1, 牛牛的好朋友羊羊帮牛牛照看着农场.有一天羊羊看到农场中逃走了k只奶牛,但是他只会告诉牛牛逃走的k只奶牛的编号之和能被n整除。你现在需要帮牛牛计算有多少种不同的逃走的奶牛群。因为结果可能很大,输出结果对1,000,000,007取模。
例如n = 7 k = 4:
7只奶牛依次编号为0到6, 逃走了4只
编号和为7的有:{0, 1, 2, 4}
编号和为14的有:{0, 3, 5, 6}, {1, 2, 5, 6}, {1, 3, 4, 6},{2, 3, 4, 5}
4只牛的编号和不会大于18,所以输出5.

输入描述:
输入包括一行,两个整数n和k(1 ≤ n ≤ 1000),(1 ≤ k ≤ 50),以空格分割。


输出描述:
输出一个整数表示题设所求的种数。
示例1

输入

7 4

输出

5
这里面有个压缩状态很重要。
原来是dp[][][]
但是我们的递推公式中,可以观察出始终是需要用dp[i-1][][]l来算dp[i][][],dp[i-1]之前的都不需要了,所以我们没必要把之前的都保存下来(三维数组就是都保存下来了)
但是这里还需要注意一点,代码中的计算公式是 dp[j][t] = (dp[j][t] + dp[j - 1][((t + n) - i) % n]) ;
但真实的递推公式是:dp[i][j][t]=dp[i−1][j][t]+dp[i−1][j−1][((t+n)−j)%n]
所以需要注意,因为代码中我们是二维数组,所以要保证在计算dp[j][t] 时,后面用到的dp[j][t] 和dp[j - 1][((t + n) - i) % n]都是上一个i得到的结果(才能对应三维的递推公式)。(就是说当计算i=2时的dp[j][t],dp[j][t] 和dp[j - 1][((t + n) - i) % n]都必须是i=1时得到的结果。)dp[j][t] 和等号左边的相同,按照编译器的处理顺序,用到的肯定是修改之前的值,所以必然是i=1时的结果,要保证dp[j - 1][((t + n) - i) % n]是上一轮的值,那么我们的第二层循环中j必须由大倒小变化,不然d[2][j-1][]在d[2][j][]之前计算,那么计算i=2的dp[j][]时,dp[j - 1][((t + n) - i) % n]就不是i=1的结果,就是i=2的结果,违背了原本(三维)的递推公式。
发表于 2017-07-12 18:42:35 回复(3)
#include<iostream>
using namespace std;
const int mod=1e9+7;
//看了楼上各位大神的代码和注释,写了一点粗鄙之见。。
//这个是通过状态压缩之后的形式了,最初的形式应该是dp[i][j][s],代表的含义是从[0,i]中取j个数,使他们的和模n的余数为s,这样的j个数的集合的个数
//状态转移方程为dp[i][j][s]=dp[i-1][j][s]+dp[i-1][j-1][(s-i+n)%n];
//转移的过程就是对于第i个数,取还是不取,如果不取,那么方案数就和i-1时的方案数相同
//如果取i的话,那么分两种情况分析,第一种情况是i<=s,此时我们需要求从前i-1个数中,取j-1个数,使得他们的和模n的余数为s-i,这样就能保证在加入i时,和模n为s
//第二种情况是i>s,那么s-i为负数,注意到本题要求的是组成和为n的倍数,也即所有模n为0的数,因此这种情况下将(s-i)%n表示成(s-i+n)%n即可满足要求,因为((s-i+n)%n+i)%n=s;
//这个式子对于第一种情况也成立,因此和在一起就好了
int dp[55][1005];
int main()
{
    int n,k;
    while(cin>>n>>k)
    {
        dp[0][0]=1;
        for(int i=0;i<n;i++)
        {
            for(int j=k;j>=1;j--)//状态压缩,道理和01背包一样
            {
                for(int s=0;s<n;s++)
                {
                    dp[j][s]=(dp[j][s]+dp[j-1][(n+s-i)%n])%mod;
                }
            }
        }
        cout<<dp[k][0]<<endl;//最后输出取k个使他们的和模n的余数为0的所有集合的数目
    }
    return 0;
}
发表于 2017-06-18 16:55:03 回复(3)
//先用比较直观的做法,用三维数组保存每个状态
//dp[i][j][s]表示前i只牛选择j头,其和除以n的余数为s的个数
/*那么状态方程即:
当s>i:
dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - i];
当s<i:
dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - i + n];
综合一下
即为:
dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][(s - i + n) % n];
*/

//这样就能解决这个问题,但是dp数组太大,超过内存限制,因此,使用滚动数组代替
#include<iostream>

using namespace std;

int dp[1005][55][1005] = { 0 };
int main()
{
	int n, k;
	//n = 7, k = 4;
	cin >> n >> k;
	int i, j, s;
	const int mod = 1000000007;
	dp[0][1][0] = 1;
	for (i = 1; i<n; i++)
	{
		dp[i][0][0] = 1;//初始条件设置好
		for (j = 1; j <= k; j++)
		{
			for (s = 0; s<n; s++)
			{
				dp[i][j][s] = (dp[i - 1][j][s] + dp[i - 1][j - 1][(s - i + n) % n]) % mod;
			}
		}
	}
	cout << dp[n - 1][k][0] << endl;
	system("pause");
	return 0;
}

//升级版
#include<iostream>

using namespace std;

int dp[2][55][1005] = { 0 };
void clear(int i)
{
	for(int j=0;j<55;j++)
		for(int s=0;s<1005;s++)
			dp[i][j][s]=0;
}
int main()
{
	int n, k;
	//n = 7, k = 4;
	cin >> n >> k;
	int i, j, s;
	const int mod = 1000000007;
	dp[0][1][0] = 1;
	for (i = 1; i<n; i++)
	{
		clear(i&1);
		dp[(i - 1) % 2][0][0] = 1;//初始条件设置好,缺少了这句,运行不正确,观察内存发现应该加这句
		for (j = 1; j <= k; j++)
		{
			for (s = 0; s<n; s++)
			{
				dp[i%2][j][s] = (dp[(i-1) % 2][j][s] + dp[(i - 1) % 2][j - 1][(s - i + n) % n]) % mod;
			}
		}
	}
	cout << dp[(i-1) % 2][k][0] << endl;
	system("pause");
	return 0;
}

//还可以继续优化,参考大佬的做法
//http://blog.csdn.net/sinat_33718563/article/details/74221986 //http://blog.csdn.net/xiaxzhou/article/details/73381206 //↑大佬的博客↑

//再升级版
#include <iostream>  
using namespace std;
const int modMin = 1e9 + 7;
int main()
{
	int dp[55][1005] = { 0 };//加上这句比较好
	dp[0][0] = 1;
	int n, k;
	while (cin >> n >> k)
	{
		for (int i = 0; i<n; i++)
		{
			for (int j = k; j >= 1; j--)
			{
				for (int s = 0; s<n; s++)
				{
					dp[j][s] = (dp[j][s] + dp[j - 1][(n + s - i) % n]) % modMin;
				}
			}
		}
		cout << dp[k][0] << endl;
	}
	return 0;
}


编辑于 2017-07-24 15:21:39 回复(1)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int k = in.nextInt();
        final int MOD = 1000000007;

        int[][] dp = new int[k + 1][n];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = Math.min(k, i); j >= 1; j--) {
                for (int l = 0; l < n; l++) {
                    dp[j][l] = (dp[j][l] + dp[j - 1][(l + n - (i - 1)) % n]) % MOD;
                }
            }
        }

        System.out.println(dp[k][0]);
    }
}
发表于 2017-07-23 16:30:07 回复(0)
import java.util.Scanner;
public class Main {
    private static final int mod = 1000_000_007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        System.out.println(escapeFarm(n, k));
    }

    /**
     * 从0~n-1的n个数中,取出k个
     * @param n n个数
     * @param k 取出k个
     * @return 组合数
     */
    public static int escapeFarm(int n, int k) {
        int[][] dp = new int[k+1][n]; //状态转移矩阵
        //初始赋值 ,i = 0时, 存在1个数,选出0个,余n为0,选出1个,余n为0,有1个
        dp[0][0] = dp[1][0] = 1;
        for (int i = 1; i < n; i++) {   //i 从1到n-1,算到n-1即为0~n-1中,选出k个数,其和余n为0
//            for (int j = 1; j <= Math.min(i+1, k); j++) {    //最少选1个数,最多选k个数
            for (int j = Math.min(i+1, k); j > 0; j--) {        //这个地方必须要倒序,因为j与j-1的值相关,即计算j时,j-1的值不能改变
                for (int l = 0; l < n; l++) {
                    dp[j][l] =(dp[j][l] + dp[j-1][(l-i+n)%n])%mod;
                }
            }
        }
        return dp[k][0];
    }
}
本来对于状态压缩不太熟悉,看了第一个牛人的答案之后才明白,贴出自己的代码,留作纪念
发表于 2017-07-06 21:53:50 回复(3)
importsys
 
 
def AA():
    whileTrue:
        line = sys.stdin.readline().strip()
        ifline == '':
            break
        linesplit = line.split(' ')
        n = int(linesplit[0])
        k = int(linesplit[1])
        ifk == 1:
            print(1)
            continue
        dp = [[0forf in range(n)] forj in range(k)]
        dp[0][0] = 1
        fori in range(1, n):
            forj in range(min(i, k - 1), - 1, -1):
                forf in range(n - 1, - 1, -1):
                    ifj == 0:
                        iff <= i:
                            dp[j][f] = 1
                        continue
                    dp[j][f] += dp[j - 1][f - i]
        print(dp[k - 1][0]  % 1000000007)
 
 
AA()
然而只能过80% O(kn^2)
发表于 2017-06-17 16:40:13 回复(2)
# python多需要的时间太长了,智能过80
import sys
def function(n,k):
    dp = [[0 for i in range(n+1)] for i in range(k+1)]
    dp[0][0] = 1
    for i in range(1,n+1):
        for j in range(k,0,-1):
            for t in range(0,n):
                dp[j][t] = (dp[j][t] + dp[j - 1][((t + n) - i) % n]) % 1000000007
    return dp[k][0]
nums = list(map(int,sys.stdin.readline().strip().split()))
print(function(nums[0],nums[1]))
编辑于 2019-07-18 17:33:50 回复(0)
#include<iostream>
using namespace std;
#define mod 1000000007
int main()
{
    int n,k;
    while(cin>>n>>k)
    {
        int dp[51][1000]={0};
        dp[0][0]=1;
        for(int i=0;i<n;i++)
        {
            for(int j=k;j>=1;j--)
            {
                for(int s=0;s<n;s++)
                    dp[j][s]=(dp[j][s]+dp[j-1][(s-i+n)%n])%mod;
            }
        }
        cout<<dp[k][0]<<endl;
    }
    return 0;
}
发表于 2017-07-31 08:38:12 回复(0)
在前i只牛中选取j只,使得他们的编号之和与n的余数为r,方式数为dp[i][j][r]。
- 如果不选取第i只牛,则选取方式数为在前i-1只牛中选取j只,方式数为dp[i-1][j][r]
- 如果选取第i只牛,则选取方式数为在前i-1只牛中选取j-1只,方式数为dp[i-1][j-1](r+n-i)%n]
因此:dp[i][j][r]=dp[i-1][j][r]+dp[i-1][j-1](r+n-i)%n]
状态压缩:dp[j][r]=dp[j][r]+dp[j-1](r+n-i)%n]
此时如果j从0到k,计算dp[i][j][r]时会覆盖掉dp[i-1][j][r]的值,因此需要从后往前计算

编辑于 2017-07-23 17:37:51 回复(0)
import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        System.out.println(solve(n, k));
    }

    private static int solve(int n, int k) {
        int[][] dp = new int[k + 1][n];
        dp[0][0] = dp[1][0] = 1;
        int[] temp = new int[n];
        for (int i = 1; i < n; i++) {
            for (int j = Math.min(k, i + 1); j > 0; j--) {
                copyArray(dp[j], temp, n);
                for (int p = 0; p < n; p++) {
                    int r = p - i;
                    if (r < 0) r += n;
                    dp[j][p] = add(temp[p], dp[j - 1][r]);
                }
            }
        }
        return dp[k][0];
    }

    private static void copyArray(int[] from, int[] to, int length) {
        for (int i = 0; i < length; i++)
            to[i] = from[i];
    }

    private static int add(int a, int b) {
        int c = a + b;
        if (c >= MOD) c -= MOD;
        return c;
    }
}
发表于 2017-06-17 21:49:26 回复(0)