递推DP HDOJ 5459 Jesus Is Here

题意：简单来说就是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+, 6+, 所以能够解释：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 = ( + 5 - 3) + ( + 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 <cstdio>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <string>

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: 0

i:1 len:1 sz:1 ans:0

id:

i:2 len:2 sz:0 ans:0

id: 0

i:3 len:3 sz:1 ans:0

id: 2

i:4 len:5 sz:1 ans:0

id: 0 5

5

i:5 len:8 sz:2 ans:5

id: 2 5 10

35

i:6 len:13 sz:3 ans:16

id: 0 5 10 13 18

5535

i:7 len:21 sz:5 ans:88

id: 2 5 10 13 18 23 26 31

3535535

i:8 len:34 sz:8 ans:352

id: 0 5 10 13 18 23 26 31 34 39 44 47 52

553553535535

i:9 len:55 sz:13 ans:1552

id: 2 5 10 13 18 23 26 31 34 39 44 47 52 57 60 65 68 73 78 81 86

35355353553553535535

i:10 len:89 sz:21 ans:6512

id: 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 10

7 112 115 120 123 128 133 136 141

553553535535535355353553553535535

i:11 len:144 sz:34 ans:27753

i:12 len:233 sz:55 ans:117392

i:13 len:377 sz:89 ans:497728

i:14 len:610 sz:144 ans:2107952

i:15 len:987 sz:233 ans:8930608

i:16 len:1597 sz:377 ans:37829456

i:17 len:2584 sz:610 ans:160251245

i:18 len:4181 sz:987 ans:148231586

i:19 len:6765 sz:1597 ans:222584546

i:20 len:10946 sz:2584 ans:507962972

i:21 len:17711 sz:4181 ans:132054082

i:22 len:28657 sz:6765 ans:505562166

i:23 len:46368 sz:10946 ans:31951635

i:24 len:75025 sz:17711 ans:102724512

i: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”

巴特西

递推DP HDOJ 5459 Jesus Is Here

最新文章

热门文章