A和E是签到题，就不写题解了。这里写一个C的贪心做法：（要用到面向对象的思路）首先预处理将所有的1连续段设置成一个类（结构体），这个结构体有连续段长度、中间的休息时间两个变量。很明显，对于给定的连续的‘1’，最终的最优工作方式是尽量平均的分配。例如，总共10天连续工作，若安排2天休息，那么一定是
展开全文
思路：dp[i][j][k] 表示对于前i天一共工作了j天现在连续工作了k天的最小花费 滚动数组优化掉第一维(不然会MLE)if(s[i]=='0') 为0只能休息dp[j][0]=min(dp[j][0],dp[j][k])if(s[i]=='1')dp[j][0]=min(dp[j][0],d
展开全文
C：思路：dp.定义dp[i][j]为前i天工作了j天的最小代价.思考如何转移：当第i天为0时,直接可以从i-1继承.那么为什么要继承？为了后续的计算.当第i天为1时.先继承i-1,然后再加入第i天去更新.如果更新？枚举到i的连续天数。列如1 1 0 0 0 1 1 1.我们当前位置i为最后一个1,
展开全文
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 405;
int dp[2][N][N];//dp(i,j,k)表示前i天工作
展开全文
链接：https://ac.nowcoder.com/acm/problem/21675来源：牛客网 题目描述 Rabbit大学毕业后找到了一份实习工作，如果实习通过她就转正了。 实习期共有N天，其中有几天公司集体放假，Rabbit不用上班，剩下时间她可以选择工作或者休息。Rabbit工作总是越来越
展开全文
用一个二维数组dp[i][j]来表示工作i天，连续工作j天那么得到状态转移方程dp[i][j]=(dp[i-1][j-1])+j （如果当前字符为'1'）最终只要遍历dp数组，找到最长天数ans（并且它满足dp[i][j]<=K，即题目中说的总体力消耗不超过K） #include <bi
展开全文
原题解链接：https://ac.nowcoder.com/discuss/151166
动态规划:
当s[i]=′1′s[i]='1's[i]=′1′时可以选择休息和工作，当s[i]=′0′s[i]='0's[i]=′0′时只能休息
理解一、
我们用dp[i][j][k]dp[i][j][k]dp
展开全文
//头文件int n,k;string str;//f[i][j] //在前i天已经工作了j天//f[i][j][p] //多了一维p（现在已经连续工作了多少天）//f[j][p] //采用就地滚动去掉第一维int f[405][405];int main
展开全文
C、Rabbit的工作(1) 参考题解7QQQQQQQ orz 一开始我打算用的函数对字符串进行从0分隔，然后对每连续的1，一直工作到不能工作在休息，然后重新工作。但是WA的理所当然……那没办法阿，只能想想别的思路了 正解：动态规划 我们表示前i天工作了j天，现在连续工作k天的最小体力花费。那么对
展开全文
直接找答案会超内存；dp[i][j][k]表示到达第i个点时，已经工作j天，连续工作了k天如果当前为0dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][k])为1dp[i][j][k]=min(dp[i][j][k],dp[i-1][j-1][k-1]+1)当k==0时，
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
