P4158 [SCOI2009]粉刷匠
我们不妨先考虑只有一行的情形。
我们做两个前缀和\(red_i,bule_i\)分别表示前\(i\)个里有多少个红色块和蓝色块。
设\(f[i][k]\)为做到第\(i\)块，此时用了\(k\)次涂刷的最大收益。
我们思考如下问题：既然重复涂色没有收益，那么我们强制让我们的涂色方案没有重叠的情况，即让我们对于这一行的方案如下图：
可以看出一段木块被分割成若干块（无色代表没涂色。
我们只要从\(i\)向前枚举上一段的终点在哪即可转移，对于\(i\)这块不涂色的情况我们直接拿\(i - 1\)的答案来覆盖即可
所以对于一条木块我们有了\(O(m^3)\)的做法来求出\(f\)
for(int r = 1;r <= m; r){for(int k = 1;k <= m; k){f[r][k] = f[r - 1][k];for(int l = 1;l <= r; l){f[r][k] = std::max(f[l - 1][k - 1] red[r] - red[l - 1],f[r][k]);f[r][k] = std::max(f[l - 1][k - 1] bule[r] - bule[l - 1],f[r][k]);}}}我们接下来考虑我们做完了一条木块怎么统计答案：
for(int to = t;to >= 0;-- to) for(int k = 0;k <= std::min(m,(ll)to); k) fans[to] = std::max(fans[to],fans[to - k] f[m][k]),ans = std::max(ans,fans[to]); 类似于一维背包即可。(注意枚举\(k\)时不要超出数组\(f\)的大小，因为这个我调了好久)
所以最后的复杂度是\(O(n * (m ^ 3 tm))\)
喜闻乐见的代码环节
#include<iostream>#include<cstdio>#include<cstring>#define ll long longll n,m,t,ans = 0,f[55][55];ll red[55],bule[55];ll fans[2505];void init(){memset(f,0,sizeof(f));memset(red,0,sizeof(red));memset(bule,0,sizeof(bule));}int main(){//freopen("q.in","r",stdin);//freopen("q.out","w",stdout);memset(fans,0,sizeof(fans));scanf("%lld%lld%lld",&n,&m,&t);for(int i = 1;i <= n; i){init();char s[55];scanf("%s",s 1);for(int i = 1;i <= m; i){red[i] = red[i - 1];bule[i] = bule[i - 1];if(s[i] == '0')red[i] ;elsebule[i] ;}for(int r = 1;r <= m; r){for(int k = 1;k <= m; k){f[r][k] = f[r - 1][k];for(int l = 1;l <= r; l){f[r][k] = std::max(f[l - 1][k - 1] red[r] - red[l - 1],f[r][k]);f[r][k] = std::max(f[l - 1][k - 1] bule[r] - bule[l - 1],f[r][k]);}}}//for(int i = 1;i <= m; i,puts(""))//for(int k = 1;k <= m; k)//std::cout<<f[i][k]<<" "; for(int to = t;to >= 0;-- to) for(int k = 0;k <= std::min(m,(ll)to); k) fans[to] = std::max(fans[to],fans[to - k] f[m][k]),ans = std::max(ans,fans[to]); }std::cout<<ans<<std::endl; } 赞 (0)