经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
BZOJ1925: [Sdoi2010]地精部落(dp)
来源:cnblogs  作者:自为风月马前卒  时间:2018/12/7 9:33:21  对本文有异议

题意

题目链接

Sol

不会做Orzzzz

想到了和题解一样的方程,但是根本不会转移

具体题解看这里

大致思路就是先推一波性质,然后对于最后一个位置上的数\(i\),分两种情况讨论一下:与\(i - 1\)相邻 / 不相邻,

  1. #include<bits/stdc++.h>
  2. #define chmin(x, y) (x = x < y ? x : y)
  3. #define chmax(x, y) (x = x > y ? x : y)
  4. using namespace std;
  5. const int MAXN = 5001, INF = 2e9 + 10;
  6. inline int read() {
  7. char c = getchar(); int x = 0, f = 1;
  8. while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
  9. while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  10. return x * f;
  11. }
  12. int f[2][MAXN], N, mod;
  13. int add(int x, int y) {
  14. return x + y >= mod ? x + y - mod : x + y;
  15. }
  16. int add2(int &x, int y) {
  17. return x = (x + y >= mod ? x + y - mod : x + y);
  18. }
  19. int mul(int x, int y) {
  20. return 1ll * x * y % mod;
  21. }
  22. int main() {
  23. N = read(), mod = read();
  24. f[0][1] = 1; int o =1;
  25. for(int i = 2; i <= N; i++, o ^= 1) {
  26. fill(f[o] + 1, f[o] + N + 1, 0);
  27. for(int j = 1; j <= i; j++)
  28. f[o][j] = add(f[o][j - 1], f[o ^ 1][i - (j - 1)]);
  29. }
  30. int ans = 0;
  31. for(int i = 1; i <= N; i++) add2(ans, f[o ^ 1][i]);
  32. printf("%d\n", mul(ans, 2));
  33. return 0;
  34. }
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号