首页 > 代码库 > bzoj3791 作业
bzoj3791 作业
Description
众所周知，白神是具有神奇的能力的。
比如说，他对数学作业说一声“数”，数学作业就会出于畏惧而自己完成；对语文作业说一声“语”，语文作业就会出于畏惧而自己完成。
今天，语文老师和数学老师布置了许多作业，同学们纷纷寻找白神寻求帮助。白神作为一个助人为乐的人，便答应下来。
回到家，白神将这N份作业按顺序摊开，发现语文作业数学作业混在一起，这就让白神苦恼起来，他如果对连续一段作业喊出“数”，那么里面的语文作业就会由于过于慌乱而写满错解，不过如果白神再对其喊一声“语”，它又会写满正确答案。
虽然白神很强大，但是能力还是有限制的，一天只能使用K次，现在，白神想知道他能正确的完成多少份作业。
Input
第一行两个整数N，K。
第二行N个0或者1表示这份作业是语文作业还是数学作业。
Output
输出一个整数，表示白神能正确完成的作业数。
Sample Input
5 2
0 1 0 1 0
0 1 0 1 0
Sample Output
4
HINT
100%的数据中N ≤ 100000，K<=50.
因为是覆盖k段，最多可以有2k-1段01相间的区间
然后f[i][j][0/1]表示前i个涂j段，并且最后一段是0/1的方案数
#include<cstdio>#include<iostream>using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int a[100010];int f[100010][100][2];int n,m;int main(){ n=read();m=2*read()-1; for (int i=1;i<=n;i++)a[i]=read(); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { f[i][j][0]=max(f[i-1][j][0],f[i-1][j-1][1])+(a[i]==0); f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0])+(a[i]==1); } printf("%d\n",max(f[n][m][0],f[n][m][1])); return 0;}
bzoj3791 作业
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。