首页 > 其他 > 详细

bzoj 1296

时间:2015-08-12 01:02:30      阅读:174      评论:0      收藏:0      [点我收藏+]

技术分享

15年市选的T2原题哟=v=。。。不过我当时以为能竖着画就一直想不出啊QAQAQAQAQ

好吧对每个木板:a[i][0/1]为前缀和,d[i][j]为画i次长度为j的正确粉刷的格子数

所以d[j][k]=max(d[j][k],d[j-1][v]+max(a[k][1]-a[v][1],a[k][0]-a[v][0]))

得出c[i][j](第i个木板用j时间正确粉刷的格子数)然后背包问题就出来了。。。

4层循环有点恶心。。。但数据弱的话就乱搞乱搞乱搞啦。。。

技术分享
 1 #include<bits/stdc++.h>
 2 #define inc(i,l,r) for(i=l;i<=r;i++)
 3 #define dec(i,l,r) for(i=l;i>=r;i--)
 4 #define inf 1e9
 5 #define NM 60
 6 #define mem(a) memset(a,0,sizeof(a))
 7 using namespace std;
 8 int a[NM][2],d[NM][NM],c[NM][NM],ans[3000],i,n,m,p,k,v,j,s,tmp[3000];
 9 char x[NM][NM];
10 int main(){
11     scanf("%d%d%d",&n,&m,&p);
12     inc(i,1,n)
13     scanf("%s",x[i]);
14     inc(i,1,n){
15         mem(a);mem(d);
16         inc(j,1,m){
17             a[j][1]=a[j-1][1];a[j][0]=a[j-1][0];
18             if(x[i][j-1]==1)a[j][1]++;else a[j][0]++;
19         }
20         inc(j,1,m)
21         inc(k,1,m)
22         inc(v,0,k-1)
23         d[j][k]=max(d[j][k],d[j-1][v]+max(a[k][1]-a[v][1],a[k][0]-a[v][0]));
24         inc(j,1,m)c[i][j]=d[j][m];
25     }
26     inc(i,1,n){
27     inc(j,1,m)
28     dec(k,p,j)
29     ans[k]=max(ans[k],tmp[k-j]+c[i][j]);
30     inc(j,1,p)tmp[j]=ans[j];
31     }
32     inc(i,1,p)
33     s=max(s,ans[i]);
34     printf("%d",s);
35     return 0;
36     
37 }
View Code

 

bzoj 1296

原文:http://www.cnblogs.com/onlyRP/p/4722711.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!