逃离农场--动态规划

偏执的太偏执、 2022-06-13 09:07 163阅读 0赞

**题目：**

牛牛在农场饲养了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\[j\]\[s\]这个是通过状态压缩后的形式，最初的形式应该是dp\[i\]\[j\]\[s\]，代表从\[0,i\]中取j个数，使他们的和与n的模余数为s，这样的j的数的集合的个数。

状态转移方程：

dp[i][j][s]=(dp[i-1][j][s]+dp[i-1][j-1][(n+s-i)%n])

转移的过程就是第i个数取还是不取，如果不取，那么就和方法i-1的个数相同；如果取第i个数的话，那么就需要分两种情况，因为第i个数可能大于s，也有可能小于等于s。 **情况1：**若i<=s,此时我们需要从前i-1个数中取j-1个数，使他们的和与n的模为s-i。这样就能保证在加入i时，和模n等于s。情况2：如果i>s,那么i-s为负数，注意本题的要求是组成和为n的倍数，因此这种情况下需要将(s-i)%n表示为（s-i+n）%n，因为

**((s-i+n)%n+i)%n=s。这个式子对于第一种情况也成立，因此合在一起就可以了。**

**代码：**

#include <iostream>
    using namespace std;
    const int modMin=1e9+7;
    int main()
      {
        int dp[55][1005];
        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;
      }