題目鏈接：https://ac.nowcoder.com/acm/contest/3002/I
題目描述：

題意：：“nico” 計 分，“niconi” 計 分，“niconiconi” 計 分。給一字符串問最大價值為多少。

解法：dp【i】前 i 個字符最大價值。

可得轉(zhuǎn)移方程：

(i >= 3 && substr(i-3 , i) == “nico”)dp[i] = max(dp[i] , dp[i-3]+a)

(i >= 5 && substr(i-5 , i) == “niconi”)dp[i] = max(dp[i] , dp[i-5]+b)

(i >= 9 && substr(i-9 , i) == “niconiconi”)dp[i] = max(dp[i] , dp[i-9]+c)

代碼：

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long const int maxn=3e5+5; char q[maxn]; ll dp[maxn]; ///注意：需要使用ll，因為a，b，c最大為1e9 int main() {int a,b,c;int n;scanf("%d%d%d%d",&n,&a,&b,&c);string s;cin>>s;memset(dp,0,sizeof(dp));dp[0]=0;for(int i=1;i<n;i++){dp[i]=dp[i-1];if(i>=3&&s.substr(i-3,4)=="nico"){dp[i]=max(dp[i],dp[i-3]+a);}if(i>=5&&s.substr(i-5,6)=="niconi"){dp[i]=max(dp[i],dp[i-5]+b);}if(i>=9&&s.substr(i-9,10)=="niconiconi"){dp[i]=max(dp[i],dp[i-9]+c);}}printf("%lld\n",dp[n-1]); }

總結(jié)

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

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