【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;
}
目录
打赏
0
0
0
0
4
分享
相关文章
codeforces 285C - Building Permutation
题目大意是有一个含n个数的数组,你可以通过+1或者-1的操作使得其中的数是1--n中的数,且没有重复的数。 既然是这样的题意,那么我就应该把原数组中的数尽量往他最接近1--n中的位置放,然后求差绝对值之和,但有多个数,怎么使他们和最小,这样就要对其进行排序了,直接按大小给它们安排好位置,然后计算。
54 0
AtCoder Beginner Contest 216 F - Max Sum Counting (降维 背包dp)
AtCoder Beginner Contest 216 F - Max Sum Counting (降维 背包dp)
179 0
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
137 0
AtCoder Beginner Contest 214 F - Substrings(subsequence DP)
AtCoder Beginner Contest 214 F - Substrings(subsequence DP)
114 0
AtCoder Beginner Contest 218 C - Shapes (模拟)
AtCoder Beginner Contest 218 C - Shapes (模拟)
178 0
AtCoder Beginner Contest 217 F - Make Pair (区间dp)
AtCoder Beginner Contest 217 F - Make Pair (区间dp)
146 0
AtCoder Beginner Contest 176 D - Wizard in Maze(01BFS)
AtCoder Beginner Contest 176 D - Wizard in Maze(01BFS)
133 0
AtCoder Beginner Contest 133 E - Virus Tree 2(组合数学)
AtCoder Beginner Contest 133 E - Virus Tree 2(组合数学)
129 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等