【 HDU - 5459】Jesus Is Here（dp）

题干：

I've sent Fang Fang around 201314 text messages in almost 5 years. Why can't she make sense of what I mean? 
``But Jesus is here!" the priest intoned. ``Show me your messages." 
Fine, the first message is s1=‘‘c"s1=‘‘c" and the second one is s2=‘‘ff"s2=‘‘ff". 
The ii-th message is si=si−2+si−1si=si−2+si−1 afterwards. Let me give you some examples. 
s3=‘‘cff"s3=‘‘cff", s4=‘‘ffcff"s4=‘‘ffcff" and s5=‘‘cffffcff"s5=‘‘cffffcff". 

``I found the ii-th message's utterly charming," Jesus said. 
``Look at the fifth message". s5=‘‘cffffcff"s5=‘‘cffffcff" and two ‘‘cff"‘‘cff" appear in it. 
The distance between the first ‘‘cff"‘‘cff" and the second one we said, is 55. 
``You are right, my friend," Jesus said. ``Love is patient, love is kind. 
It does not envy, it does not boast, it is not proud. It does not dishonor others, it is not self-seeking, it is not easily angered, it keeps no record of wrongs. 
Love does not delight in evil but rejoices with the truth. 
It always protects, always trusts, always hopes, always perseveres." 

Listen - look at him in the eye. I will find you, and count the sum of distance between each two different ‘‘cff"‘‘cff" as substrings of the message. 

Input

An integer T (1≤T≤100)T (1≤T≤100), indicating there are TT test cases. 
Following TT lines, each line contain an integer n (3≤n≤201314)n (3≤n≤201314), as the identifier of message.

Output

The output contains exactly TT lines. 
Each line contains an integer equaling to: 

∑i<j:sn[i..i+2]=sn[j..j+2]=‘‘cff"(j−i) mod 530600414,∑i<j:sn[i..i+2]=sn[j..j+2]=‘‘cff"(j−i) mod 530600414,

where snsn as a string corresponding to the nn-th message.

Sample Input

9 5 6 7 8 113 1205 199312 199401 201314

Sample Output

Case #1: 5 Case #2: 16 Case #3: 88 Case #4: 352 Case #5: 318505405 Case #6: 391786781 Case #7: 133875314 Case #8: 83347132 Case #9: 16520782

题目大意：

   字符串s[1]="c",s[2]="ff",s[i]=s[i-2]+s[i-1](i>=3);

   对于每个n,求s[n]中所有的任意两个字符c的距离之和f[n]；

解题报告：

   同时维护五个值然后dp就行了。对于f[i]，为f[i-1]+f[i-2]左右两侧分别的 + 左侧对右侧造成的贡献。所以求f[i]的同时维护一下每个字符串的  所有c到右侧的距离和  ，  所有c到左侧的距离和，c的个数，字符串长度。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 3e5 + 5; const ll mod = 530600414LL; ll l[MAX],r[MAX],f[MAX],len[MAX],c[MAX]; int main() {len[3] = 3;len[4] = 5;l[4] = 3;r[4] = 3;c[4] = 1;l[5] = 1 + 6;r[5] = 3 + 8;c[5] = 2;len[5] = len[4] + len[3];//8l[6] = 3 + 6 + 11;//l[4] + len[4]*c[5] + l[5]r[6] = 3 + 8 + 11;//r[5] + c[4]*len[5] + r[4]c[6] = c[5]+c[4];len[6] = len[5]+len[4];f[5] = 5;f[6] = 16;for(int i = 7; i<=201314; i++) {len[i] = len[i-1] + len[i-2];c[i] = c[i-1]+c[i-2];l[i] = l[i-2] + len[i-2]*c[i-1] + l[i-1];r[i] = r[i-1] + c[i-2]*len[i-1] + r[i-2];f[i] = f[i-1]+f[i-2] + (r[i-2]-c[i-2]+mod)*(c[i-1]) + c[i-2]*(l[i-1]);l[i]%=mod;r[i]%=mod;f[i]%=mod;len[i]%=mod;c[i]%=mod;}int t,n,iCase=0;cin>>t;while(t--) {scanf("%d",&n);printf("Case #%d: %lld\n",++iCase,f[n]%mod);}return 0 ; }

 

总结

以上是生活随笔为你收集整理的【 HDU - 5459】Jesus Is Here（dp）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。