選nico都對惹

題目描述

nico平時最喜歡說的口頭禪是niconiconi~。有一天nico在逛著名彈幕網(wǎng)站"niconico"的時候驚異的發(fā)現(xiàn)，n站上居然有很多她的鬼畜視頻。其中有一個名為《讓nico為你腦的視頻吸引了她的注意。她點進去一看，就被洗腦了

"niconicoh0niconico*^vvniconicoG(vniconiconiconiconiconicoG(vniconico......"彈幕中剛開始有很多“nico*1 nico*2”等計數(shù)菌，但到后面基本上都是“計數(shù)菌陣亡”的彈幕了。nico也想當(dāng)一回計數(shù)菌。她認為："nico" 計 a 分，"niconi" 計 b 分，"niconiconi" 計 c 分。她拿到了一個長度為 n 的字符串，請幫她算出最大計數(shù)分數(shù)。
注：已被計數(shù)過的字符不能重復(fù)計數(shù)！如"niconico"要么當(dāng)作"nico"+"nico"計 a * 2 分，要么當(dāng)作"niconi"+"co"計 b 分。

輸入

19 1 2 5 niconiconiconiconi~

輸出

7

思路：

我楞了半天沒發(fā)現(xiàn)是個線性DP問題，tcl

dp[i]表示前i - 1個最大的分數(shù)，那么轉(zhuǎn)移方程很明顯，首先dp[i + 1] = dp[i]，如果當(dāng)前沒有新的nico···出現(xiàn)就是前面的分數(shù)了，如果當(dāng)前字母是o，并且前面有nic，說明當(dāng)前位置出現(xiàn)了一個新的nico，那么dp[i + 1] = max(dp[i + 1]，dp[i - 3] + a)，就是把當(dāng)前分數(shù)和前面的三個字母和當(dāng)前的o拼成nico后加上前面的位置的分數(shù)

如果當(dāng)前字母是i，并且前面是n，說明出現(xiàn)了一個ni，前面如果還出現(xiàn)了nico，說明出現(xiàn)了niconi，那么dp[i + 1] = max(dp[i + 1]，dp[i - 5] + b)；為什么不和nico + a分比較呢？這個肯定出現(xiàn)再niconi之前，那么上面的過程一定計算過了，每次都會把前面的分數(shù)直接給當(dāng)前位置，所以不用比較了。

如果是i，前面是niconicon，說明構(gòu)成了niconiconi，和上面一樣，dp[i + 1] = max(dp[i + 1]，dp[i - 8] + c，dp[i - 8] + a + b，dp[i - 8] + a + a）

最后輸出dp[len]就好了

#include <bits/stdc++.h> using namespace std; const int N = 301000; char s[N]; typedef long long ll; ll dp[N]; ll n, a, b, c; int main() {ios::sync_with_stdio(0);cin >> n >> a >> b >> c;cin >> s;memset(dp, 0, sizeof dp);int len = strlen(s);for (int i = 0; i < len; i++){dp[i + 1] = dp[i];if(s[i] == 'o' && i - 3 >= 0){if(s[i - 1] == 'c' && s[i - 2] == 'i' && s[i - 3] == 'n'){dp[i + 1] = max(dp[i], dp[i - 2] + a);}}else if(s[i] == 'i'){if(i - 5 >= 0){if(s[i - 1] == 'n' && s[i - 2] == 'o' && s[i - 3] == 'c' && s[i - 4] == 'i' && s[i - 5] == 'n'){dp[i + 1] = max(dp[i + 1], dp[i - 4] + b);}}if(i - 9 >= 0){if(s[i - 1] == 'n' && s[i - 2] == 'o' && s[i - 3] == 'c' && s[i - 4] == 'i' && s[i - 5] == 'n'&& s[i - 6] == 'o' && s[i - 7] == 'c' && s[i - 8] == 'i' && s[i - 9] == 'n'){dp[i + 1] = max(dp[i + 1], dp[i - 8] + c);dp[i + 1] = max(dp[i + 1], dp[i - 8] + b + a);dp[i + 1] = max(dp[i + 1], dp[i - 8] + a + a);}}}}cout << dp[len] << "\n";return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的2020牛客寒假算法基础集训营1 I nico和niconiconi的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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