FUZ2204环形DP

文章目录[x]
  1. 1:原题链接
  2. 2:题意
  3. 3:思路
  4. 4:参考代码

csdn博客链接:https://nuoyanli.blog.csdn.net/article/details/105260334


原题链接

http://acm.fzu.edu.cn/problem.php?pid=2204

题意

给出个小球,每个小球只能涂黑色或者是白色,规定个连续的不能是同种颜色,问有多少种涂色方法?答案取模

思路

我们将问题变成,求用组成长度为的环,环中不能超过有连续的方案数,答案

首先,这是环形是毋容置疑的,我们先抛开环形这个问题考虑线形的

  • 表示到第个位置,这个位置种类为的组成的方案数,又因为的情况是一样的,所以任取一种做答案即可。

  • 状态转移

    for (int i = 1; i <= n; i++) {
      dp[i][0] = 1;
      for (int j = 0; j < 2; j++) {
        for (int k = 1; k < min(i, 7); k++) {
            dp[i][j] = (dp[i][j] + dp[i - k][!j]) % mod;
        }
      }
    }
    

     

现在回归到环形这个限制,对于上面推的状态显然是具有后效性的,涉及到重复计算,拆环我们可以考虑枚举起点的状态:

  • 由于先前说的的状态是对应的,我们以为例枚举起点的状态

    1

    10
    100
    1000
    10000
    100000
    1000000

  • 我们之后的所有状态都可以由上面这些两两拼接。
  • 最后我们计算结果的时候,如果结尾和开头枚举的物品种类相同,要保证答案合法那么只需要保证结尾连续的个数+开头连续的个数即可。

与线形的相比,状态转移不变,就多枚举了开始位置和状态而已。

参考代码

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>

//#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#define kB kush_back
#define FI first
#define SE second
//#define in
#define RI register
#define m_k(a, b) make_kair(a, b)
#define debug(a) cout << "---" << a << "---" << endl
#define debug_(a, b) cout << a << "---" << b << endl
const double pi = acos(-1.0);
const double eps = 1e-9;
typedef long long LL;
const int N = 1e5 + 10;
const int M = 1e3 + 10;
const int mod = 2015;
const LL inf = 0x3f3f3f3f;
const double f = 2.32349;
LL dp[N][2], n, t;
void solve() {
  IOS;
  int k = 0;
  cin >> t;
  while (t--) {
    cin >> n;
    cout << "Case #" << ++k << ": ";
    LL ans;
    if (n <= 6) {//不足7直接算
      ans = 1;
      for (int i = 1; i <= n; i++) {
        ans = (ans + ans) % mod;
      }
    } else {
      ans = 0;
      for (int st = 1; st < 7; st++) {
        memset(dp, 0, sizeof(dp));
        dp[st][0] = 1;
        for (int i = st + 1; i <= n; i++) {
          for (int j = 0; j < 2; j++) {
            if (i == n && j == 0) {
              for (int k = 1; k < min(i, 7 - st); k++) {
                  dp[i][j] = (dp[i][j] + dp[i - k][!j]) % mod;
              }
            } else {
              for (int k = 1; k < min(i, 7); k++) {
                  dp[i][j] = (dp[i][j] + dp[i - k][!j]) % mod;
              }
            }
          }
        }
        ans = (ans + dp[n][0] + dp[n][1]) % mod;
      }
      ans = (ans * 2) % mod;
    }
    cout << ans << endl;
  }
}
signed main() {
#ifdef in
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  solve();
  return 0;
}

 


点赞
  1. Chter说道:

    ∠( ᐛ 」∠)_

  2. 霸道总裁的绝世小受说道:

    0v0

  3. 囧囧倉说道:

    0v0

  4. 枢木朱雀说道:

    0v0

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像