一个跟字符串相关的dp问题,还是挺简单的
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> typedef long long ll; using namespace std; long long dp[300005]; int main() { //一道关于字符串水题,每一个点就进行一次更新,如果可以更新,就更新,如果不可以更新,就直接等于上一个的值(每次更新进行三次,一次是a的,一次是b的,一次是c的) int n,a,b,c; //n是字符串的长度,a是nico的分值,b是niconi的分值,c是niconiconi的分值 cin >> n >> a >> b >> c; string s; cin >> s; for(int i=3;i<n;i++) { dp[i]=dp[i-1]; //dp[i+1]至少是dp[i],如果可以更新,则按照下面的三个条件进行更新 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); } } cout << dp[n-1] << endl; return 0; }