原題鏈接：Problem - D - Codeforces

題面：?

大概意思就是讓你在翻轉01串不超過k次的情況下，使得a*（0的最大連續長度）+（1的最大連續長度）最大（1<=a<=n）。輸出n個數，第i個數代表a=i時的最大值。

思路：可以發現n<=3000，我們可以用O(n^2)的復雜度來求解。首先我們先假設最長連續0串在左邊，最長的連續1串在右邊，一開始最樸素的思想就是：

枚舉最長0串的左端點l和右端點r，并且使它合法。設區間[l,r]中1的個數為x，也就是說[l,r]變成全0串需要的操作數為x。然后O(n^2)求出區間[r+1,n]我們能得到的最長1串，長度為y（此時我們能進行的最大操作數為k-x）。我們定義mp[i]：0串長度為i時，1串的最長長度為mp[i]。然后我們更新mp[x]為max(mp[r-l+1],y)即可。

因為這是0串在左，1串在右，所以我們還需要將字符串翻轉然后再這樣處理一次。

最后輸出的時候，每次我們只需要遍歷mp，a*i+mp[i]取max即可。

當然這樣子操作的總復雜度是O(n^4)，我們肯定是不能接受的，那么怎么能讓它復雜度降下來呢？我們可以利用dp來預處理，用dp[i][j]來表示[i~n]區間，操作數最大為j時，1串的最大長度。

具體實現見代碼注釋。

int n,k;
int mp[maxn];
//表示連續0的長度為i的時候，最長連續1的長度最大為mp[i]
string x;
void f() {vector<vector<int>>dp(n+2,vector<int>(k+2));//dp[i][j]表示[i~n]區間，操作數最大為j時，連續1的最大長度。 vector<int>sum(n+2);//sum[i]表示[1,i]中字符1的個數 string s=" "+x;//下標從1開始，防止數組越界 for(int i=n; i>=1; i--) {//預處理出i~n的字符串在操作數為k時候變為1的最大連續串長度dp[i]=dp[i+1]; //大區間可以由小區間的方案轉移過來 ,因為在相同操作數下，[i,n]的最長連續1串 >=[i+1,n]的最長連續1串 int cost=0;for(int j=i; j<=n; j++) {cost+=(s[j]=='0');if(cost<=k) dp[i][cost]=max(dp[i][cost],j-i+1);//如果合法，則答案取max else break;//后面的cost都大于k了，直接break }for(int j=1; j<=k; j++) dp[i][j]=max(dp[i][j],dp[i][j-1]);//大的操作數方案可以由小的操作數方案轉移過來，因為你用x次操作能辦到的，用x+1次操作也一定能辦到 }mp[0]=max(mp[0],dp[1][k]);//將全是1，沒有0的情況特殊處理 for(int i=1; i<=n; i++)sum[i]=sum[i-1]+(s[i]=='1');//預處理前綴1的個數 for(int i=1; i<=n; i++) {for(int j=i; j<=n; j++) {if(sum[j]-sum[i-1]>k)continue;//如果操作數大于k了則不合法，continue mp[j-i+1]=max(mp[j-i+1],dp[j+1][k-sum[j]+sum[i-1]]);//j-i+1為連續0的長度，k-sum[j]+sum[i-1]為剩下的操作數 }}
}
void solve() {cin>>n>>k>>x;for(int i=0; i<=n; i++) mp[i]=-1;//初始化為-1 f();//處理0串在左，1串在右的情況 reverse(x.begin(),x.end()),f();//等于處理1串在左，0串在右的情況 for(int i=1; i<=n; i++) {int ans=0;for(int j=0; j<=n; j++) {//當0的長度為j時 if(mp[j]!=-1)ans=max(ans,i*j+mp[j]);}cout<<ans<<" ";}cout<<endl;
}

?