http://codeforces.com/PRoblemset/problem/776/C
题意就是给你一个字符串，之后给你26个数即a[i]，那么a[i]表示在字母表中以第i个字符开头的子串的最大长度。在以上条件下你要把这个字符串划分为若干个不重叠的子串。 你要输出的结果有 1. 划分子串的个数 2. 在你划分中，出现的最长子串的长度 3. 划分子串的最小个数
那么我们可以用状态转移的思想，每个字符代表一个状态即可。
#include <bits/stdc++.h>#define maxs 202020#define mme(i,j) memset(i,j,sizeof(i))using namespace std;#define inf 0x3f3f3f3f3f3fconst long long int mod = 1e9+7;string s;int a[maxs];int n,dp[maxs],mn[maxs];int lng[maxs];int main(){ cin>>n; cin>>s; for(int i=0;i<26;i++) cin>>a[i]; dp[0]=1;//dp【i】代表第i位的字符所能划分的个数 lng[0]=0;//表示lng【i】在第i个字符中所能划分的最长的子串长度 for(int i=1;i<=n;i++) { int len = inf; mn[i]=inf;//mn[i]表示在第i位划分的个数。 lng[i]=-inf; for(int j=i-1;j>=0;j--) { int id = s[j]-'a'; len = min( len,a[id] ); if(len <i-j) break; dp[i] = ( dp[i]+dp[j] )%mod; //简单的想一下，这个转移方法 lng[i] = max( lng[i],max( i-j,lng[j] ) );//同上 mn[i] = min( mn[i],mn[j]+1 );//同上 } } cout<<dp[n]<<endl; cout<<lng[n]<<endl; cout<<mn[n]<<endl; return 0;}新闻热点
疑难解答
