NC21675Rabbit的工作(1)

链接：https://ac.nowcoder.com/acm/problem/21675
来源：牛客网

题目描述

Rabbit大学毕业后找到了一份实习工作，如果实习通过她就转正了。
实习期共有N天，其中有几天公司集体放假，Rabbit不用上班，剩下时间她可以选择工作或者休息。Rabbit工作总是越来越累，可是每当她休息时，她就重新充满了能量。简而言之，Rabbit第一天工作时这一天会消耗体力1，连续第二天工作时这一天会消耗体力2，连续第三天工作时这一天会消耗体力3，以此类推......每当她休息后，工作的第一天又会消耗体力1。
为了让boss满意，Rabbit想工作尽量多的天数，但是懒惰的Rabbit又想让自己的总体力消耗不超过K。

输入描述:

第一行两个整数N，K。

第二行一个长度为N的01字符串。如果第i个字符为‘1’，表示这一天Rabbit可以选择工作或者休息，否则这一天Rabbit放假。

输出描述:

输出Rabbit最多能工作的天数。

思路：

$dp[i][j][k]$ 前 $i$ 天工作 $j$ 天且连续工作 $k$ 天

分情况讨论：

当字符为0时，此天休息， $dp[i][j][0]=min(dp[i-1][j][x]) x\in[0,400]$

当字符为1时，此天可以工作也可以休息，休息同上。

工作时：

$dp[i][j][k]=min(dp[i-1][j-1][k-1])+k,dp[i][j][k])$

为减少维度，采用滚动数组，观察状态转移方程知 $dp[i]$ 只和 $[i]与[i-1]$ 有关为省去此维度就倒序 $j$ ，类似于01背包的降维滚动。

降维：

$dp[j][k]$ 表示工作 $j$ 天且连续 $k$ 天

当休息时： $dp[j][0]=min(dp[j][0],dp[j][k])$

当工作时： $dp[j][k]=min(dp[j][k],dp[j-1][k-1]+k)$

其中 $k$ 可正序枚举也可逆序枚举

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 10;
int dp[410][410];
string str;
int main(){
    int n, k;
    cin >> n >> k;
    cin >> str;
    for(int i=0;i<=n;++i){
        for(int j=0;j<=n;++j){
            dp[i][j]=0x7f7f7f7f;
        }
    }
    dp[0][0]=0;
    for(int i = 1; i <= n; ++i) {
        for(int j = i; j > 0; --j) {
            for(int k = 1; k <= j; ++k) {
                if(str[i - 1] == '0') {
                    dp[j][0] = min(dp[j][0], dp[j][k]);
                } else {
                    dp[j][0] = min(dp[j][0], dp[j][k]);
                    dp[j][k] = min(dp[j][k], dp[j - 1][k - 1] + k);
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(dp[i][j] <= k) {
                ans = i;
            }
        }
    }
    cout << ans << endl;
}