題意

給出一個字符串 和每個字符的限制數量ai 讓我們隨意的切割成多個字符串 使得每一個字符串中的特定字符所在的子串長度len<=ai
求一共有多少個符合題目要求的方案 求其中最長的一個串長度是多少 求其中最少能分成多少個串
長度最大為1000

分析

明顯可以用搜索 不過復雜度指數級 計數問題
考慮dp
對于第i個字符 他可以考慮從i-ai+1開始往后到i分割字符 我們這里可以枚舉分割的位置
然后記錄下來 那么對于第i個字符 我們知道他前面所有字符的分割數量 就可以更新第i個字符的分割方案 假設用dp[i]表示從1到第i個字符的可行分配方案 那么dp[i] +=dp[j]其中合法情況之和 就可以計數出所有情況的可能

code

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> using namespace std; const int mod = 1e9+7; char a[1010]; int dp[1010],mmin[1010],mmax,res[26]; bool judge(int pos,int l){for(int i=pos-l+1;i<=pos;i++){if(res[a[i]-'a']<l)return 0;}return 1; } int main() {int n;scanf("%d%s",&n,a+1);for(int i=0;i<26;i++)scanf("%d",&res[i]);dp[0]=1;for(int i=1;i<=n;i++){mmin[i] = mod;for(int j=1;j<=i;j++){if(judge(i,j)){//如果符合條件 就把方案數轉移到更長的字符下dp[i] = (dp[i]+dp[i-j])%mod;mmin[i] = min(mmin[i],mmin[i-j]+1);//兩個dp變量 都要更新 這里就是要把段數一并更新 mmax = max(mmax,j);}}}printf("%d\n%d\n%d\n",dp[n],mmax,mmin[n]);return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 766C - Mahmoud and a Message dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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