【noi 2.6_9271】奶牛散步(DP)

这题与前面的“踩方格”重复了,而且是大坑题!题目漏写了取模12345的条件!

详细解析请见我之前的博文——http://www.cnblogs.com/konjak/p/5936888.html

而这坑在我打了高精+滚动之后才知道。。我先把这个代码贴上来。。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6
 7 struct node{int s[510];int l;}
 8 f[3],c;//1010
 9
10 int mmax(int x,int y) {return x>y?x:y;}
11 node pplus(node a,node b)
12 {
13     c.l=mmax(a.l,b.l);
14     memset(c.s,0,sizeof(c.s));
15     for (int i=1;i<=c.l;i++)
16     {
17       c.s[i]+=a.s[i]+b.s[i];
18       c.s[i+1]+=c.s[i]/10;
19       c.s[i]%=10;
20     }
21     if (c.s[c.l+1]) c.l++;
22     return c;
23 }
24
25 int main()
26 {
27     int n;
28     scanf("%d",&n);
29     f[1].l=1,f[1].s[1]=3;
30     f[2].l=1,f[2].s[1]=7;
31     int u,v,w;
32     u=0;
33     for (int i=3;i<=n;i++)
34     {
35       v=(u+2)%3,w=(u+1)%3;//v=(u+3-1)%3,w=(u+3-2)%3;
36       f[u]=pplus(pplus(f[v],f[v]),f[w]);
37       u=(u+1)%3;
38     }//f[i]=pplus(pplus(f[i-1],f[i-1]),f[i-2]);
39     int t=(u+2)%3;//(u+3-1)%3;
40     if (n<3) t=n;
41     for (int i=f[t].l;i>=1;i--)
42       printf("%d",f[t].s[i]);
43     printf("\n");
44     return 0;
45 }

高精+滚动

AC代码是这样的——

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6
 7 int f[3];
 8 int main()
 9 {
10     int n;
11     scanf("%d",&n);
12     f[1]=3,  f[2]=7;
13     int u,v,w;
14     u=0;
15     for (int i=3;i<=n;i++)
16     {
17       v=(u+2)%3,w=(u+1)%3;
18       f[u]=(2*f[v]+f[w])%12345;
19       u=(u+1)%3;
20     }
21     if (n<3) printf("%d\n",f[n]);
22     else printf("%d\n",f[(u+2)%3]);
23     return 0;
24 }

滚动

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6
 7 long long f[1010];
 8
 9 int main()
10 {
11     int n;
12     scanf("%d",&n);
13     f[1]=3,  f[2]=7;
14     for (int i=3;i<=n;i++)
15        f[i]=(2*f[i-1]+f[i-2])%12345;
16     printf("%lld\n",f[n]);
17     return 0;
18 }

不滚动

时间: 10-14

【noi 2.6_9271】奶牛散步(DP)的相关文章

9271:奶牛散步

---恢复内容开始--- 9271:奶牛散步 查看 提交 统计 提问 总时间限制:  10000ms 单个测试点时间限制:  1000ms 内存限制:  131072kB 描述 从一个无限大的矩阵的中心点出发,一步只能向右走.向上走或向左走.恰好走N步且不经过已走的点 共有多少种走法? 输入 一个数字,代表N,N<=1000 输出 输出有多少方案 样例输入 2 样例输出 7 由图,把方案数看作一棵树,f[n]表示到第n步有多少种走法,易得f[n]为x个三步+y个两步的和,而x的值等于f[n-1]

奶牛抗议 DP 树状数组

奶牛抗议 DP 树状数组 USACO的题太猛了 容易想到\(DP\),设\(f[i]\)表示为在第\(i\)位时方案数,转移方程: \[ f[i]=\sum f[j]\;(j< i,sum[i]-sum[j]\ge0) \] \(O(n^2)\)过不了,考虑优化 移项得: \[ f[i]=\sum f[j]\;(j< i,sum[i]\ge sum[j]) \] 这时候我们发现相当于求在\(i\)前面并且前缀和小于\(sum[i]\)的所有和,这就可以用一个树状数组优化了,在树状数组维护下标为

noi 9271 奶牛散步

题目链接:http://noi.openjudge.cn/ch0206/9271/ 同noi 踩方格,但是题目有问题,%12345,我也是看了discuss才知道的. #include <bits/stdc++.h> using namespace std; unsigned long long d[1005]; int main() { d[1] = 3; d[2] = 7; for(int i=3;i<=1001;i++) d[i] = (2*d[i-1] + d[i-2])%123

BZOJ_1616_[Usaco2008_Mar]_Cow_Travelling_游荡的奶牛_(DP)

描述 http://www.lydsy.com/JudgeOnline/problem.php?id=1616 给出一张图,有些点不能走,给出起始点和结束点,以及时间,求在该时间到达结束点的方案数. 分析 直接DP即可. \(f[i][j][k]\)表示在\(i\)时间走到\((j,k)\)的方案数. 在\(i\)时间从点\((a,b)\)走到\((c,d)\): \(f[i][c][d]+=f[i-1][a][b]\). 1 #include <bits/stdc++.h> 2 using

BZOJ 1616 [Usaco2008 Mar]Cow Travelling游荡的奶牛:dp【网格型】

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1616 题意: 有一个n*m的网格. '.'表示平坦的草地,'*'表示挡路的树(不能走). 有一只奶牛,第0秒时在(r1,c1),第t秒时在(r1,c2). 它每一秒钟都会向上下左右任一方向走一格,不会停留不动. 问你在这t秒钟内,奶牛可能的移动路径数. 题解: 表示状态: dp[i][j][k]:表示在第k秒,走到了位置(i,j)时的方案数. 找出答案: ans = dp[r2][c2]

[Usaco2008 Mar]Cow Travelling游荡的奶牛[简单DP]

Description 奶牛们在被划分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上游走,试图找到整块草地中最美味的牧草.Farmer John在某个时刻看见贝茜在位置 (R1, C1),恰好T (0 < T <= 15)秒后,FJ又在位置(R2, C2)与贝茜撞了正着. FJ并不知道在这T秒内贝茜是否曾经到过(R2, C2),他能确定的只是,现在贝茜在那里. 设S为奶牛在T秒内从(R1, C1)走到(R2, C2)所能选择的路径总数,F

[noip模拟]散步&lt;dp&gt;

题目链接:http://begin.lydsy.com/JudgeOnline/problem.php?id=2097 这题A的时候,百感交集五味杂陈............ 就这么一道看起来简单的不得了的裸的一件内衣都不剩的dp我就卡了几天 唉,看来我这种蒟蒻是没有救了. 看完题后,有些朋友可能会和我一样去定义一个数组f[i,j,l,r]表示第一个人在i,j位置,第二个人在l,r位置 然后一看n是小于等于100就放心大胆的继续码代码下去了 但实际上这东西如果单纯循环不仅仅会爆时间,还要爆内存(

BZOJ 1875: [SDOI2009]HH去散步( dp + 矩阵快速幂 )

把双向边拆成2条单向边, 用边来转移...然后矩阵乘法+快速幂优化 --------------------------------------------------------------------------------------------- #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MOD = 45989; const int

NOI 1995 合并石子 区间DP

题目 题目描述 在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分. 试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分. 输入输出格式 输入格式: 数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数. 输出格式: 输出共2行,第1行为最小得分,第2行为最大得分. 输入输出样例 输入样例#1: 4 4 5 9 4 输出样例#1: 43 54 分析