首页 > 代码库 > bzoj3791作业*

bzoj3791作业*

bzoj3791作业

题意:

对一个01序列进行染色,每次能将一个区间染上色(可覆盖之前染的),共能染k次,求最大正确染色个数。n≤100000,m≤50。

题解:

结论:染k次最多能把序列分成2*k-1段。故dp即可:

f[i][j][0]=max(f[i+1][j+1][1]+a[i]==1,f[i+1][j][0]+a[i]==0)

f[i][j][1]=max(f[i+1][j][1]+a[i]==1,f[i+1][j+1][0]+a[i]==0)

代码:

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 110 6 #define INF 0x3fffffff 7 using namespace std; 8  9 inline int read(){10     char ch=getchar(); int f=1,x=0;11     while(ch<0||ch>9){if(ch==-)f=-1; ch=getchar();}12     while(ch>=0&&ch<=9)x=x*10+ch-0,ch=getchar();13     return f*x;14 }15 int n,f[2][maxn][3],k,x,y; bool a[maxn*1000];16 int main(){17     n=read(); k=2*read()-1; inc(i,1,n)a[i]=read(); x=0; y=1;18     for(int i=n;i>=1;i--){19         f[x][k+1][0]=f[x][k+1][1]=-INF;20         inc(j,1,k){21             f[y][j][0]=max(f[x][j][0]+(a[i]==0),f[x][j+1][1]+(a[i]==1));22             f[y][j][1]=max(f[x][j+1][0]+(a[i]==0),f[x][j][1]+(a[i]==1));23         }24         swap(x,y);25     }26     printf("%d",max(f[x][1][0],f[x][1][1])); return 0;27 }

 

20160831

bzoj3791作业*