【牛客 - 373B】666RPG(线性计数dp)
題干:
鏈接:https://ac.nowcoder.com/acm/contest/373/B
來(lái)源:牛客網(wǎng)
在歐美,“666”是個(gè)令人極其厭惡和忌諱的數(shù),被稱(chēng)為“野獸數(shù)”。
相傳,尼祿,這位歷史上以暴君著稱(chēng)的古羅馬皇帝,在一次羅馬大火后,無(wú)端指控是基督徒焚燒了羅馬,并對(duì)他們進(jìn)行大肆鎮(zhèn)壓。尼祿死后,部分基督徒出于對(duì)尼祿的恐懼,相信他并沒(méi)有死去,而且還會(huì)回到羅馬來(lái)。圣經(jīng)《新約·啟示錄》中說(shuō),有一頭野獸“因傷致死,但是它的致命傷又治好了”。“你所看見(jiàn)的獸先前有,如今沒(méi)有,將要從無(wú)底坑里上來(lái)……可以計(jì)算野獸的數(shù)目,他的數(shù)目是六百六十六。” 基督徒把“666”稱(chēng)為“野獸數(shù)”,相信尼祿就是復(fù)活的野獸。
關(guān)于“野獸數(shù)666”有許多趣聞。比如:
美國(guó)前總統(tǒng)里根在其離任前,曾打算退休后移居貝萊爾市克勞德大街666號(hào)別墅,然而當(dāng)他得知這一邪惡的門(mén)牌號(hào)時(shí),頓時(shí)大驚失色。
無(wú)獨(dú)有偶,在尼克松當(dāng)政時(shí),國(guó)務(wù)卿基辛格博士也碰上了“666”的調(diào)侃。美國(guó)著名數(shù)學(xué)科普作家馬丁·加德納在其名著《不可思議的矩陣博士》中,采用以代碼數(shù)字替換英文字母的方式,把26個(gè)英文字母變成一個(gè)以6為首項(xiàng)、公差為6的等差數(shù)列:
A(6),B(12),C(18),D(24),E(30),F(36),G(42),H(48),I(54), J(60),K(66),L(72),M(78),N(84),O(90),P(96),Q(102),R(108),S(114),T(120),U(126),V(132),W(138),X(144),Y(150),Z(156)。
然后,把基辛格(Kissinger)的姓氏字母,變換為代碼數(shù)字求和:66+54+114+114+54+84+42+30+108=666,正好是個(gè)“野獸數(shù)”。
以前對(duì)希特勒和墨索里尼也進(jìn)行過(guò)類(lèi)似的計(jì)算。并且,經(jīng)過(guò)一些有心人的“考證”,許多壞事、惡事都與“野獸數(shù)666”有關(guān)。比如,“666”就正好是賭場(chǎng)輪盤(pán)上數(shù)字的和。所以,西方人甚至不少名流、學(xué)者都對(duì)“野獸數(shù)666”諱莫如深。
?
不過(guò)在數(shù)學(xué)上,666的確有許多奇妙之處。如:
?1、666是前七個(gè)素?cái)?shù)的平方和??22+32+52+72+112+132+172=666?22+32+52+72+112+132+172=666
?2、?(6+6+6)+(63+63+63)=666?(6+6+6)+(63+63+63)=666。
?3、?(6+6+6)+2×(6+6+6)2=666?(6+6+6)+2×(6+6+6)2=666。
?4、?13+23+33+43+53+63+53+43+33+23+13=666?13+23+33+43+53+63+53+43+33+23+13=666。
?---廢話到此為止?
?
lililalala正在玩一種有?N?N個(gè)回合的回合制RPG游戲,初始分?jǐn)?shù)為0,第?i?i個(gè)回合lililalala有如下兩種選擇。
??? A.將分?jǐn)?shù)加上?ai?ai
??? B.將分?jǐn)?shù)?×-1?×-1
lililalala同樣也很討厭野獸數(shù)?666?666,但是他很卻喜歡數(shù)字?-666?-666。他想知道有多少種不同的方案使得?N?N個(gè)回合后分?jǐn)?shù)變?yōu)?-666?-666且在任何一個(gè)回合之后分?jǐn)?shù)都不為?666?666。
如果兩種方案有任何一個(gè)回合選擇不同,就認(rèn)為這兩種方案是不同的。
答案請(qǐng)對(duì)?108+7?108+7取模。
輸入描述:
?輸入包含兩行。
第一行一個(gè)整數(shù)?N(1≤N≤300)?N(1≤N≤300)。
第二行?N?N個(gè)整數(shù)?a1a2a3...an(-666≤?a1a2a3...an≤666)?a1a2a3...an(-666≤?a1a2a3...an≤666)。
輸出描述:
輸出一行一個(gè)整數(shù)--符合條件的不同方案數(shù)。示例1
輸入
復(fù)制
3 -333 -333 -333輸出
復(fù)制
1說(shuō)明
?僅一種符合條件的方案
第一回合選擇將分?jǐn)?shù)?×?1?×?1。分?jǐn)?shù)為?0?0
第二回合選擇將分?jǐn)?shù)加上?-333?-333。分?jǐn)?shù)為?-333?-333
第三回合選擇將分?jǐn)?shù)加上?-333?-333。分?jǐn)?shù)為?-666?-666
示例2
輸入
復(fù)制
3 333 333 333輸出
復(fù)制
0示例3
輸入
復(fù)制
13 518 -643 -503 424 -76 -18 547 26 51 -647 -457 -5 329輸出
復(fù)制
2題目大意:
? ?給定n個(gè)數(shù),n個(gè)回合,第i個(gè)回合可以有兩種選擇:將當(dāng)前分?jǐn)?shù)*-1,或?qū)?dāng)前分?jǐn)?shù)+= a[i]
解題報(bào)告:
? ?dp[i][j]代表前i個(gè)回合,分?jǐn)?shù)到達(dá)j的方案數(shù)。注意到可能有負(fù)數(shù),平移一個(gè)長(zhǎng)度zero。又注意到可能會(huì)超內(nèi)存,滾動(dòng)數(shù)組優(yōu)化一下。如果遇到==666的,就不轉(zhuǎn)移,就好了。
AC代碼:
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const double PI = acos(-1.0); const int MAX = 2e5 + 5; int n; int a[MAX]; ll dp[2][105555]; const ll mod = 1e8+7 ; const int zero = 50000; int main() {cin>>n;int sum = 0;for(int i = 1; i<=n; i++) cin>>a[i];dp[0][0+zero] = 1;int flag = 0;for(int i = 1; i<=n; i++) {flag ^=1;for(int j = -40000; j<=40000; j++) {if(j == 666) continue;dp[flag][j+zero] += dp[flag^1][-j+zero];dp[flag][j+zero] += dp[flag^1][j-a[i]+zero];dp[flag][j+zero] %= mod;}memset(dp[flag^1],0,sizeof dp[flag^1]);} printf("%lld\n",dp[flag][-666 + zero]);return 0 ;}?
總結(jié)
以上是生活随笔為你收集整理的【牛客 - 373B】666RPG(线性计数dp)的全部?jī)?nèi)容,希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇: 读取慢了50%!曝苹果M2版MacBoo
- 下一篇: ACM所有算法大全(持续更新)