【AtCoder Beginner Contest 253】E - Distance Sequence

简介: 笔记

题意


5.png


思路


6.png7.png

代码


  • 前缀和 + 动态规划
int n, m, k;
int f[M], s[M];
void solve() {
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) f[i] = 1; // i == 1;
  for (int i = 2; i <= n; i++) { // i > 1
    s[0] = 0;
    for (int j = 1; j <= m; j++)
      s[j] = (s[j - 1] + f[j]) % mod;
    int sum = s[m];
    for (int j = 1; j <= m; j++) {
      int l = max(1ll, j - k + 1);
      int r = min(m, j + k - 1);
      if(k > 0) f[j] = (sum - s[r] + s[l - 1] + mod) % mod;
      else f[j] = sum % mod;
    }
  }
  int res = 0;
  for (int i = 1; i <= m; i++) res = (res + f[i]) % mod;
  cout << res << endl;
}
相关文章
Codeforces Round #192 (Div. 2) (330B) B.Road Construction
要将N个城市全部相连,刚开始以为是最小生成树的问题,其实就是一道简单的题目。 要求两个城市之间不超过两条道路,那么所有的城市应该是连在一个点上的,至于这个点就很好找了,只要找到一个没有和其他点有道路限制的即可。
57 0
UVa11296 - Counting Solutions to an Integral Equation(枚举技巧)
UVa11296 - Counting Solutions to an Integral Equation(枚举技巧)
59 0
UVa11565 - Simple Equations
UVa11565 - Simple Equations
58 0
|
人工智能 BI
AtCoder Beginner Contest 216 F - Max Sum Counting (降维 背包dp)
AtCoder Beginner Contest 216 F - Max Sum Counting (降维 背包dp)
148 0
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
128 0
|
机器学习/深度学习
AtCoder Beginner Contest 218 C - Shapes (模拟)
AtCoder Beginner Contest 218 C - Shapes (模拟)
159 0
|
人工智能
atcoder AtCoder Beginner Contest 210 D - National Railway(dp)
atcoder AtCoder Beginner Contest 210 D - National Railway(dp)
128 0
AtCoder Beginner Contest 176 D - Wizard in Maze(01BFS)
AtCoder Beginner Contest 176 D - Wizard in Maze(01BFS)
124 0
AtCoder Beginner Contest 214 F - Substrings(subsequence DP)
AtCoder Beginner Contest 214 F - Substrings(subsequence DP)
105 0

热门文章

最新文章