nico和niconiconi

昨天打了一會比賽頭疼，就把比賽鴿了，今天補題，寫這道題，覺得字符串的substr()這個函數挺好用，理解了題意后，推一下，動態方程就出來了

題解：

如果當前為nico那么dp[i]=max(dp[i-3]+a,dp[i])，以此類推就能推出動態轉移方程，因為當前如果要取的話，就會對之前的狀態影響，所以找到不受影響的加上取的，和當前不取的狀態比較即可，01背包的思路

subst(i,len)從i開始，長度為len的字符串，就相當于從字符串中截斷一部分

AC代碼：

#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=3e5+5; ll dp[maxn]; string s; int main() {ll n,a,b,c;cin>>n>>a>>b>>c;cin>>s;int len=s.size();for(int i=1;i<len;i++){dp[i]=dp[i-1];if(i>2&&s.substr(i-3,4)=="nico"){dp[i]=max(dp[i],dp[i-3]+a);}if(i>4&&s.substr(i-5,6)=="niconi"){dp[i]=max(dp[i],dp[i-5]+b);}if(i>8&&s.substr(i-9,10)=="niconiconi"){dp[i]=max(dp[i],dp[i-9]+c);}}cout<<dp[n-1]<<endl; }

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。