基础算法题——nico和niconiconi（动态规划）

短命女 2023-07-13 10:40 27阅读 0赞

# nico和niconiconi（动态规划） #

## 前言 ##

本人为一名普通二本学校自动化专业的大二学生，对编程有着少许兴趣。  
动态规划有时候真的挺摸不着头绪的，希望这道题能加深我们对动态规划的理解。

## 题目 ##

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]  
[牛客网题目链接][Link 1]

## 考查重点 ##

①、列出状态转换方程  
②、判断特殊情况

## 题目分析 ##

题中要求的是最大计数分数。在同一个字符串中可能会出现不同的计分情况，我们要如何保证当前的计分是最大的计分分数呢？

计 dp\[i\]代表前 i 个字符的计数最大值。  
那么可得状态转移方程：  
if(substring(s,i,4)==nico) dp\[i\]=max(dp\[i\],dp\[i−4\]+a)  
if(substring(s,i,6)==niconi) dp\[i\]=max(dp\[i\],dp\[i−6\]+b)  
if(substring(s,i,10)==niconiconi) dp\[i\]=max(dp\[i\],dp\[i−10\]+c)  
参考：[神崎兰子][Link 2]

eg：在s=“niconiconiconiconi~”，a=1，b=2，c=5条件下  
**首先**：写出函数substring()（Java自带，C语言则要手写）  
判断s字符串最后四位、六位、十位 与 “niconiconi”前四位、六位、十位是否相等。

**其次**：dp\[i\]=dp\[i-1\]后再进行dp\[i\]=max(dp\[i\],dp\[i−x\]+y)的赋值。（x可以为4、6、10，y可以对应为a、b、c）原因有两个：  
一、在s字符串中可能会出现连续s字符串最后四位、六位、十位 与 “niconiconi”前四位、六位、十位不相等的情况。  
二、dp\[i-1\]可能会大于dp\[i−x\]+y。

当i=3时，dp\[3\]=a=1;  
当i=4时，dp\[4\]=1;  
当i=5时，dp\[5\]=max(dp\[5\],dp\[0\]+b),dp\[3\]<dp\[0\]+b=2,dp\[5\]=2;  
…  
当i=17时，dp\[17\]=max(dp\[17\],dp\[7\]+c),dp\[17\]<dp\[7\]+c=7,dp\[17\]=7;  
当i=18时，dp\[18\]=dp\[17\]，因为s\[18\]="~"，s字符串最后四位、六位、十位 与 “niconiconi”前四位、六位、十位不相等。  
通过 **dp\[i\]** 与 dp\[i\]可能出现的分数作对比，使得dp\[i\]为当前最大计分分数。  
（加粗的dp\[i\]，是指在0~i-1的dp最大值计数分数）

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    char s[300100];
    ll n, a, b, c, dp[300100], num=0;
    
    //判断字符串s后b个字符是否与"niconiconi"前b个字符相同
    bool substring(char *s, ll a, ll b)
    { 
    	ll i;
    	char ss[12]="niconiconi";
    	for(i=0; i<b&&ss[i]==s[a+i+1-b]; i++);
    	if(i==b) 
    		return true;
    	else 
    		return false;
    }
    
    int main()
    { 
    	cin>>n>>a>>b>>c>>s;
    	memset(&dp, 0, sizeof(dp));
    	for(ll i=0; i<n; i++)
    	{ 
    		if(substring(s, i, 4)&&i>=3)
    		{ 
    			dp[i]=max(dp[i],dp[i-4]+a);
    			if(dp[num]<dp[i])num=i;
    			//记录当前i的dp最大值对应下标
    		}
    		if(substring(s, i, 6)&&i>=5)
    		{ 
    			dp[i]=max(dp[i],dp[i-6]+b);
    			if(dp[num]<dp[i])num=i;
    		}
    		if(substring(s, i, 10)&&i>=9)
    		{ 
    			dp[i]=max(dp[i],dp[i-10]+c);
    			if(dp[num]<dp[i])num=i;
    		}
    		dp[i]=dp[num];	
    		//传递当前i的dp最大值
    	}
    	cout<<dp[num];
    	
    	return 0;
    }

总结：动态规划类型题，首先答案能否用递推的方式解决（一般是求最大、最小、最优），如果可以就要思考在如何构造状态转移方程。

希望能够将自己的一些学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白，我们下次见。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: /images/20230529/ab1331bbb13c441d89323f780b02a674.png
[Link 1]: https://ac.nowcoder.com/acm/problem/200657
[Link 2]: https://www.nowcoder.com/discuss/364600?type=post&order=time&pos=&page=3