网站宽度一般是多少,福建泉州做网站公司,开发公司顶名字购买房子,阿里云万网网站题意#xff1a;给出一个字符串#xff0c;去掉第i位的花费为a[i]#xff0c;求使字符串中子串不含hard的最小代价。 题解#xff1a;这题的思路还是比较套路的#xff0c; dp[i][kd]两维#xff0c;kd0表示不含d的最小花费#xff0c;1表示不含rd的#xff0c;2表示不… 题意给出一个字符串去掉第i位的花费为a[i]求使字符串中子串不含hard的最小代价。 题解这题的思路还是比较套路的 dp[i][kd]两维kd0表示不含d的最小花费1表示不含rd的2表示不含ard的3表示不含hard的 那么转移方程就显而易见了一言概之就是如果前面没有我这也要没有就这位一定要去否则不用去 代码如下 #includebits/stdc.h
using namespace std;int n,a[100010];
char s[100010];
long long dp[100010][4];int main()
{scanf(%d,n);scanf(%s,s1);for(int i1;in;i){scanf(%d,a[i]);}for(int in;i1;i--){dp[i][0]dp[i1][0];dp[i][1]dp[i1][1];dp[i][2]dp[i1][2];dp[i][3]dp[i1][3];if(s[i]d){dp[i][0]dp[i1][0]a[i];dp[i][1]min(dp[i1][0],dp[i1][1]);} if(s[i]r){dp[i][1]dp[i1][1]a[i];dp[i][2]min(dp[i1][1],dp[i1][2]);}if(s[i]a){dp[i][2]dp[i1][2]a[i];dp[i][3]min(dp[i1][2],dp[i1][3]);}if(s[i]h){dp[i][3]dp[i1][3]a[i];}}long long ans0;ansmin(min(dp[1][0],dp[1][1]),min(dp[1][2],dp[1][3]));printf(%lld\n,ans);
} #includebits/stdc.h
using namespace std;int n,a[100010];
char s[100010];
long long dp[100010][4];int main()
{scanf(%d,n);scanf(%s,s1);for(int i1;in;i){scanf(%d,a[i]);}for(int in;i1;i--){dp[i][0]dp[i1][0];dp[i][1]dp[i1][1];dp[i][2]dp[i1][2];dp[i][3]dp[i1][3];if(s[i]d){dp[i][0]dp[i1][0]a[i];dp[i][1]min(dp[i1][0],dp[i1][1]);} if(s[i]r){dp[i][1]dp[i1][1]a[i];dp[i][2]min(dp[i1][1],dp[i1][2]);}if(s[i]a){dp[i][2]dp[i1][2]a[i];dp[i][3]min(dp[i1][2],dp[i1][3]);}if(s[i]h){dp[i][3]dp[i1][3]a[i];}}long long ans0;ansmin(min(dp[1][0],dp[1][1]),min(dp[1][2],dp[1][3]));printf(%lld\n,ans);
} 转载于:https://www.cnblogs.com/stxy-ferryman/p/10344294.html
