递推DP HDOJ 5459 Jesus Is Here-白红宇

递推DP HDOJ 5459 Jesus Is Here

阅读量：6867 次

发布时间：2019-06-26

本文共 3554 字，大约阅读时间需要 11 分钟。

题意：简单来说就是sn = sn-1 + sn-2递推而来，求其中所有c字符的：∑i<j:sn[i..i+2]=sn[j..j+2]=‘‘cff"(j−i) mod 530600414

分析：一开始觉得很难下手，类似于斐波那契数列，最后的数字会很大，不能正常求解。想到试试打表找规律，结果并没有找到什么规律。。。最后也没想出什么来。赛后才恍然大悟，这是递推题，拿来别人的思路:

串长度len，串中字符c的个数num，串中所有字符c的位置之和sum，串中所有字符c之间的距离之和ans。

我们可以得到公式

一、node[i].len = node[i-1].len + node[i-2].len;

二、node[i].num = node[i-1].num + node[i-2].num;

三、node[i].sum = node[i-1].sum + node[i-2].sum + node[i-2].len*node[i-1].num。

四、node[i].ans = node[i-1].ans + node[i-2].ans+(node[i-2].len*node[i-2].num-node[i-2].sum)*node[i-1].num+node[i-1].sum*node[i-2].num;

用例子解释一下第三点和第四点：s4 = "ffcff", s5 = "cffffcff", s6 = s4 + s5 = "ffcff" + "cffffcff"，第三点：在s5中，c的下标为1,6，在s6中，下标为1+5, 6+5, 所以能够解释：node[i-2].len*node[i-1].num。第四点：因为[i-2].ans和[i-1].ans已经知道各自串c的位置和以及距离差的和，所以能够解释node[i-1].sum + node[i-2].sum，node[i-1].ans + node[i-2].ans，那么剩下的是怎么得到s5与s4的距离差的和。不考虑字符串内部的部分：[6].ans = (1 + 5 - 3) + (6 + 5 - 3)，红色代表-node[i-2].sum)*node[i-1].num，绿色代表node[i-1].sum*node[i-2].num，剩下的代表(node[i-2].len*node[i-2].num *node[i-1].num。不管怎么样，我是懂了的~

总结：这题目很好，很少接触这样的递推类型。另外，出题人的秀恩爱(表白？)的方式也让本人大开眼界，如果没看过Contest Clarifications，不知能发现多少亮点：)

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;const int N = 201314 + 10;const int INF = 0x3f3f3f3f;const int MOD = 530600414;struct DP { ll len, num, sum, ans;}dp[N];void solve(void) { dp[3].len = 3; dp[3].num = 1; dp[3].sum = 1; dp[3].ans = 0; dp[4].len = 5; dp[4].num = 1; dp[4].sum = 3; dp[4].ans = 0; for (int i=5; i<=201314; ++i) { dp[i].len = (dp[i-2].len + dp[i-1].len) % MOD; dp[i].num = (dp[i-2].num + dp[i-1].num) % MOD; dp[i].sum = (dp[i-2].sum + dp[i-1].sum + (dp[i-2].len * dp[i-1].num) % MOD) % MOD; dp[i].ans = (dp[i-2].ans + dp[i-1].ans + ((dp[i-2].len*dp[i-2].num-dp[i-2].sum)%MOD*dp[i-1].num)%MOD + dp[i-2].num * dp[i-1].sum) % MOD; }}int main(void) { solve (); int T, cas = 0; scanf ("%d", &T); while (T--) { int n; scanf ("%d", &n); printf ("Case #%d: %I64d\n", ++cas, dp[n].ans); } return 0;}

其他乱七八糟的，留个念~

id: 0i:1 len:1 sz:1 ans:0id:i:2 len:2 sz:0 ans:0id: 0i:3 len:3 sz:1 ans:0id: 2i:4 len:5 sz:1 ans:0id: 0 55i:5 len:8 sz:2 ans:5id: 2 5 1035i:6 len:13 sz:3 ans:16id: 0 5 10 13 185535i:7 len:21 sz:5 ans:88id: 2 5 10 13 18 23 26 313535535i:8 len:34 sz:8 ans:352id: 0 5 10 13 18 23 26 31 34 39 44 47 52553553535535i:9 len:55 sz:13 ans:1552id: 2 5 10 13 18 23 26 31 34 39 44 47 52 57 60 65 68 73 78 81 8635355353553553535535i:10 len:89 sz:21 ans:6512id: 0 5 10 13 18 23 26 31 34 39 44 47 52 57 60 65 68 73 78 81 86 89 94 99 102 107 112 115 120 123 128 133 136 141553553535535535355353553553535535i:11 len:144 sz:34 ans:27753i:12 len:233 sz:55 ans:117392i:13 len:377 sz:89 ans:497728i:14 len:610 sz:144 ans:2107952i:15 len:987 sz:233 ans:8930608i:16 len:1597 sz:377 ans:37829456i:17 len:2584 sz:610 ans:160251245i:18 len:4181 sz:987 ans:148231586i:19 len:6765 sz:1597 ans:222584546i:20 len:10946 sz:2584 ans:507962972i:21 len:17711 sz:4181 ans:132054082i:22 len:28657 sz:6765 ans:505562166i:23 len:46368 sz:10946 ans:31951635i:24 len:75025 sz:17711 ans:102724512i:25 len:121393 sz:28657 ans:442982018

“cff”　　“I've sent Fang Fang around 201314 text messages in almost 5 years. Why can't she make sense of what I mean?”“Love does not delight in evil but rejoices with the truth.It always protects, always trusts, always hopes, always perseveres.”“(j−i) mod 530600414,”“113 1205 199312 199401 201314”

转载于:https://www.cnblogs.com/Running-Time/p/4824329.html

你可能感兴趣的文章