牛客328B Rabbit的工作(1)

传送门:https://ac.nowcoder.com/acm/contest/328/B

题意:给你n和k,和一个长度为n的字符串,字符串中的0表示休息,1表示工作,连续工作会损耗连续的体力值,从1开始,但是休息后就重新计算体力值,一共最多损耗k点体力值,求解最多工作多少天

题解:动态规划,状态定义为,dp[j][k]表示在第i天之前工作j天,并且已经连续工作k天的情况下的最小体力花费,最后扫一遍,保存满足条件的j的最大值即可

代码如下:

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define PI acos(-1)
#define eps 1e-8
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const int maxn = 3e5 + ;
const LL INF = 1e18 + ;
const LL mod = 1e9 + ;
LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = ; while (b) {if (b % )ans = ans * a % MOD; a = a * a % MOD; b /= ;} return ans;}
double dpow(double a, LL b) {double ans = 1.0; while (b) {if (b % )ans = ans * a; a = a * a; b /= ;} return ans;}
int n, m;
char str[];
int dp[][]; int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
scanf("%d%d%s", &n, &m, str + );
memset(dp, 0x3f3f3f3f, sizeof(dp));
dp[][] = ;
//dp[j][k]表示在第i天之前工作j天,并且已经连续工作k天的情况下的最小体力花费
for (int i = ; i <= n; i++) {
for (int j = i; j >= ; j--) {
for (int k = j; k >= ; k--) {
dp[j][] = min(dp[j][], dp[j][k]);
if (str[i] == '') {
dp[j][k] = min(dp[j][k], dp[j - ][k - ] + k);
}
}
}
} int ans = ;
for (int i = ; i <= n; i++) {
for (int j = ; j <= n; j++) {
if (dp[i][j] <= m) {
ans = i;
}
}
}
cout << ans << endl;
}
上一篇:How to Reset VW Steering Assist 1S1909144P with OBDSTAR X300 DP


下一篇:Gulp安装笔记(转)已经测试过