出题人题解 | #Rabbit的工作(1)#

原题解链接：https://ac.nowcoder.com/discuss/151166

动态规划:

当$s[i]{=}^{\mathrm{\prime }}{1}^{\mathrm{\prime }}s[i]=\text{'}1\text{'}$时可以选择休息和工作，当$s[i]{=}^{\mathrm{\prime }}{0}^{\mathrm{\prime }}s[i]=\text{'}0\text{'}$时只能休息

理解一、

我们用$dp[i][j][k]dp[i][j][k]$表示考虑到第$ii$天，当前已经一共工作了$jj$天，且现在连续工作的天数为$kk$的时候剩余体力的最大值，那么我们就可以根据当前位是$00$还是$11$写出状态转移方程

当$s[i]={=}^{\mathrm{\prime }}{0}^{\mathrm{\prime }}s[i]==\text{'}0\text{'}$时 $dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])$

当$s[i]={=}^{\mathrm{\prime }}{1}^{\mathrm{\prime }}s[i]==\text{'}1\text{'}$时 $dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])$(不工作)

$dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i-1][j][k]-k-1)dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i-1][j][k]-k-1)$ (工作)

最后找到满足$dp[n][j][k]\ge 0dp[n][j][k]\; \backslash geq\; 0$ 最大的$jj$即可

理解二、

我们用$dp[i][j][k]dp[i][j][k]$表示考虑到第$ii$天，当前已经在可以选择工作和休息的日子里一共休息了$jj$天，且现在连续工作的天数为$kk$的时候剩余体力的最大值，那么我们就可以根据当前位是$00$还是$11$写出状态转移方程

当$s[i]={=}^{\mathrm{\prime }}{0}^{\mathrm{\prime }}s[i]==\text{'}0\text{'}$时 $dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])$

当$s[i]={=}^{\mathrm{\prime }}{1}^{\mathrm{\prime }}s[i]==\text{'}1\text{'}$时 $dp[i][j+1][0]=max(dp[i][j+1][0],dp[i-1][j][k])dp[i][j+1][0]=max(dp[i][j+1][0],dp[i-1][j][k])$(不工作)

$dp[i][j][k+1]=max(dp[i][j][k+1],dp[i-1][j][k]-k-1)dp[i][j][k+1]=max(dp[i][j][k+1],dp[i-1][j][k]-k-1)$(工作)

最后找到满足$dp[n][j][k]\ge 0dp[n][j][k]\; \backslash geq\; 0$ 最大的$jj$即可

贪心是不可以的，如下面的样例:

$9129\; 12$

$111111111111111111$

#include <cstdio>
#include <bits/stdc++.h>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)

typedef long long ll;
const int maxn = 405;
const ll INF = 1e18;
const ll mod=1e9+7;
const double eps = 1e-9;

int n,m;
int dp[2][maxn][maxn];
char s[maxn];

int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",s);
    int up=0;
    for(int i=0;i<n;i++) if(s[i]=='1') up++;
    mst(dp,-1);
    dp[0][0][0]=m;
    int now=0;
    for(int i=0;i<n;i++)
    {
        mst(dp[now^1],-1);
        for(int j=0;j<=up+2;j++)
        for(int k=0;k<=up+2;k++)
        {
            if(dp[now][j][k]>=0)
            {
                if(s[i]=='0') dp[now^1][j][0]=max(dp[now^1][j][0],dp[now][j][k]);
                else
                {
                    dp[now^1][j+1][0]=max(dp[now^1][j+1][0],dp[now][j][k]);
                    dp[now^1][j][k+1]=max(dp[now^1][j][k+1],dp[now][j][k]-k-1);
                }
            }
        }
        now^=1;
    }
    int flag=1;
    for(int j=0;j<=up+2&&flag;j++)
    for(int k=0;k<=up+2&&flag;k++)
    {
        if(dp[now][j][k]>=0)
        {
            printf("%d\n",up-j);
            flag=0;
        }
    }
}