「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段。。。
于是直接dp即可。。。印象中有种倒过来贪心的做法？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define ll long long #define inf 2000000000 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 n,K,ans; int a[100005],f[2][105][2]; int main() { n=read();K=read(); for(int i=1;i<=n;i++)a[i]=read(); f[1][1][a[1]]=1; for(int i=1,p=1,q=0;i<=n-1;i++,swap(p,q)) { for(int j=1;j<=K*2-1;j++) for(int x=0;x<2;x++) for(int y=0;y<2;y++) f[q][j+(x!=y)][y]=max(f[q][j+(x!=y)][y],f[p][j][x]+(a[i+1]==y)); for(int j=1;j<=K*2-1;j++) { f[p][j][0]=f[p][j][1]=0; ans=max(ans,max(f[q][j][0],f[q][j][1])); } } printf("%d\n",ans); return 0; } |
Subscribe
计数器 9863569
OI 课件=>
OI 课件=>