唔在cf上做过,A题也做过,神仙说D题也是原题
这个题就是dp了。然后数组滚动一下,很显然能住遇到 i 只与 i-1 有关,所以还是挺好滚的。
dp[i][j][k]表示到第I 天一共工作了J天连续工作了K天还剩的 体力值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
string s;
int dp[][][];
int main(){
ios::sync_with_stdio(false);
cin>>n>>k>>s;
s="*"+s;
memset(dp,-, sizeof(dp));
dp[&][][]=k;
for(int i=;i<=n;i++){
dp[i&][][]= k;
if(s[i]==''){
for(int j=;j<=i;j++){
for(int k=;k<=j;k++) {
dp[i&][j][] = max(dp[i&][j][], dp[(i-)&][j][k]);
}
}
} else{
//不工作
for(int j=;j<=i;j++){
for(int k=;k<=j;k++) {
dp[i&][j][] = max(dp[i&][j][], dp[(i-)&][j][k]);
}
}
//工作
for(int j=;j<=i;j++){
for(int k=;k<=j;k++) {
dp[i&][j][k+] = max(dp[i&][j][k+], dp[(i-)&][j-][k]--k);
}
}
}
}
int ans = ;
for(int j=;j<=n;j++){
for(int k=;k<=j;k++){
if(dp[n&][j][k]>=){
ans = max(ans,j);
}
}
}
cout<<ans<<endl;
}