原題鏈接：https://ac.nowcoder.com/acm/contest/3002/I

思路

---

一開(kāi)始想用貪心做，wa了一萬(wàn)次，后來(lái)發(fā)現(xiàn)dp才是正解

代碼

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<vector> #define ll long long using namespace std; ll n, a, b, c; char str[300001];//一大坑點(diǎn)在于必須要保留str[0]的位置，從str[1]開(kāi)始輸入字符串，否則會(huì)訪問(wèn)str[-1]，因此不能直接用string及其函數(shù)，就很蛋疼 ll dp[300001]; int main() {cin >> n >> a >> b >> c;scanf("%s", str + 1);for (int i = 1; i <= n; i++){dp[i] = dp[i - 1];if (i >= 4 && str[i - 3] == 'n' && str[i - 2] == 'i' && str[i - 1] == 'c' && str[i] == 'o')dp[i] = max(dp[i], dp[i - 4] + a);if (i >= 6 && str[i - 5] == 'n' && str[i - 4] == 'i' && str[i - 3] == 'c' && str[i - 2] == 'o' && str[i - 1] == 'n' && str[i] == 'i')dp[i] = max(dp[i], dp[i - 6] + b);if (i >= 10 && str[i - 9] == 'n' && str[i - 8] == 'i' && str[i - 7] == 'c' && str[i - 6] == 'o' && str[i - 5] == 'n' && str[i - 4] == 'i' && str[i - 3] == 'c' && str[i - 2] == 'o' && str[i - 1] == 'n' && str[i] == 'i')dp[i] = max(dp[i], dp[i - 10] + c);}printf("%lld\n", dp[n]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的nico和niconiconi题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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