題目的鏈接在這里：https://www.nowcoder.com/practice/70a03345bae6499ea4338ebc3a0b60e9

目錄

• 題目大意
• 一、示意圖
• 二、解題思路
• • 字符串加動態規劃

---

題目大意

給定一個字符串 S ，定義三種有價值的字符串： A = "nico" ，B = "niconi" , C = "niconiconi" 其中，字符串 A 的價值為 a， 字符串 B 的價值為 b，字符串 C 的價值為 c 她拿到了一個長度為 n 的字符串，你需要在其中找到一些有價值的子串 (指字符串中連續的一段)，并統計價值之和的最大值。 注：已被計算價值過的字符不能重復計算價值！如 "niconico" 要么當作 "nico" + "nico" 計 2a 分，要么當作 "niconi" + "co" 計 b 分（其中 "co" 不計分）。

---

一、示意圖

二、解題思路

字符串加動態規劃

字符串加動態規劃

代碼如下：

import java.util.*; public class Main{ public static void main(String[] args){//字符串S 不同的字符串有不同的價值Scanner sc=new Scanner(System.in);/* int n=sc.nextInt();System.out.println("n = " + n);int a=sc.nextInt();System.out.println("a = " + a);int b=sc.nextInt();System.out.println("b = " + b);int c=sc.nextInt();System.out.println("c = " + c);*/String[] nums=sc.nextLine().split(" ");int n=Integer.parseInt(nums[0]);int a=Integer.parseInt(nums[1]);int b=Integer.parseInt(nums[2]);int c=Integer.parseInt(nums[3]);//然后是長度為n的字符串String str=sc.nextLine();/*** dp[i]表示的是前i個最大值 進行一次判定 如果前三個是nico的話 那dp就是 dp[i]和dp[i-4}+a 之間的比大小*///先進行邊界判斷if(n<=3){System.out.println(0);}if(n==4){//那就按照4的進行比較if(str.equals("nico")){System.out.println(a);}else{System.out.println(0);}}int []dp=new int[n];//先進行初始化dp[0]=0;dp[1]=0;dp[2]=0;//判斷第一個是不是nico subString是左閉右開的if(str.substring(0,4).equals("nico")){dp[3]=a;}else{dp[3]=0;}//然后開始判斷for(int i=4;i<n;i++){//然后開始依次判斷 就是判斷倒數四個是不是nico//如果這些條件都不滿足的話 那也是需要進行一個傳遞的dp[i]=dp[i-1];if(str.substring(i-3,i+1).equals("nico")){//那就進行更新dp[i]=Math.max(dp[i],dp[i-3]+a);}//然后進行判定 niconiif(i>=5&&str.substring(i-5,i+1).equals("niconi")){//再進行更新 這里i-6就要成為負數了if(i==5){dp[i]=Math.max(dp[i],b);}else {dp[i] = Math.max(dp[i], dp[i - 6] + b);}}//再判斷和 niconiconi的if(i>=10&&str.substring(i-9,i+1).equals("niconiconi")){dp[i]=Math.max(dp[i],dp[i-10]+c);}}System.out.println(dp[n-1]);} }

總結

以上是生活随笔為你收集整理的java 牛客网之[动态规划 简单]NC3 nico和niconiconi的全部內容，希望文章能夠幫你解決所遇到的問題。

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