Link ：

 

Solution：

还是自己DP做少了啊，这种**题一开始还做错了

 

由于每一条木板间是独立的，且涉及到染色次数的分配

要想到对木板间进行分组DP

 

而要实现分组DP就要先求出每条木板上染色$x$次能贡献的最大答案

这个用背包DP$O(n^3)$就行了

 

Code：

#include 
     
      using namespace std;const int MAXN=55;char s[MAXN];int n,m,t,sum[MAXN],f[MAXN][2500+10],g[MAXN][MAXN],res=0;int main(){    scanf("%d%d%d",&n,&m,&t);    for(int i=1;i<=n;i++)    {        scanf("%s",s+1);memset(g,0,sizeof(g));        for(int j=1;j<=m;j++) sum[j]=sum[j-1]+(s[j]=='1');        for(int j=1;j<=m;j++) //背包DP            for(int k=1;k<=m;k++)                for(int l=0;l
     

 

Review：

还是对各类DP模型不够敏感

1、如果每组数之间相对独立且涉及到权重的分配，考虑使用分组DP（本质也是一种背包）

2、一般能化简成求前$i$个里进行$j$次操作最值问题的，使用背包DP