題干：

鏈接：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)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。