題意

給你一個字符串，問你操作后的最長串的最小值。

Solution:

首先考慮 dp 。由 k<=17 想到狀壓 dp ，但是字符集太大 2^17 ，而字符串長度 2e5 ，所以不太好直接做。

二分答案。轉為判定 mid 是否成立。還是觀察到 k<=17 ，考慮枚舉先后匹配順序，因為只需要匹配 k 次，時間復雜度 O(k2^k) 。

設 pos[i][j] 表示 [i,n] 匹配字符 j 的最早位置，那么可以 O(1) 轉移。

但是直接枚舉排列會超時。再次發揮人類智慧，用二進制來搞，復雜度就降為了 k2^k 。

總時間復雜度 O((k2^k+nk)logn) 。

總結：做 dp 題做不出來時要善于換狀態，及時排除錯誤的模型和做法。

細節：因為這里判的是 0 ，所以 k=0 需要特判。

#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define ll long long #define PII pair<int,int> #define All(a) a.begin(),a.end() using namespace std; const int mx=2e5+5; const int mxn=(1<<17)+5; int n,k,pos[17][mx],dp[mxn]; char s[mx]; bool check(int mid) {for(int i=0;i<k;i++) {int cnt=0;for(int j=n;j>=1;j--) {cnt=(s[j]=='a'+i||s[j]=='?')?cnt+1:0;if(cnt>=mid) pos[i][j]=j+mid-1;else pos[i][j]=pos[i][j+1];}}dp[0]=0;for(int i=1;i<(1<<k);i++) {dp[i]=INF;for(int j=0;j<k;j++) {if((i>>j)&1 && dp[i-(1<<j)]!=INF && pos[j][dp[i-(1<<j)]+1]) {dp[i]=min(dp[i],pos[j][dp[i-(1<<j)]+1]);}}}return dp[(1<<k)-1]!=INF; } int main() {scanf("%d%d%s",&n,&k,s+1);int l=1,r=n/k,res=0;while(l<=r) {int mid=(l+r)>>1;if(check(mid)) res=mid,l=mid+1;else r=mid-1;}printf("%d",res); }

總結

以上是生活随笔為你收集整理的【题解】CF1550E Stringforces的全部內容，希望文章能夠幫你解決所遇到的問題。

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