上网找分组背包找到这题，感觉还是很有思维性的，固写文以记之。
## 此题难点有二：
1. 首先的难点便是怎么将本题转换为背包模型。
我们可以看出对于每一天翘多少课所得到的价值都是互相独立的，那么就很容易想到将每一天都看成一个物品组，翘不同数量的课可以达到不同的**最大价值**，然后跑分组背包即可。
但由于翘课顺序不同导致的剩余价值也不同，所以直接贪心递推地删点是不可取的。
2. 于是第二个难点便是**每一天翘课所得到的最大价值**应如何计算
我们考虑搞一个辅助DP，设$s[i][j]$为第i天翘了j节课所达到的最大价值。
由于我们翘课只有从两边翘才可达到最优，那我们对于一个确定的j，**可以分别枚举左右两边翘课的数量**。
我们设$g[i][j]$为第i天第j节课的时间节点，$pm_i$为第i天不翘课的最长时间，$cl_i$表示第i天总课数，就可得到如下式子：
$$s[i][j]=Max_{(0\leq p\leq max(cl_i,k))} \begin{Bmatrix} g[i][j-p]-g[i][p]+1\end{Bmatrix}$$
$P.S.:$由于我们定义的价值是**翘课所减少的时间**，所以最后要统一用$s[i][j]=pm_i-s[i][j]$更新，这样就可以跑裸的分组背包板子啦！
放上丑陋的代码：
```cpp
#include <iostream>
#include <cstring>
using namespace std;
int s[1000][1000],f[1000],g[1000][1000];
int n,m,k,sum; char c;
int dis(int i,int x,int y){return (g[i][x]-g[i][y]+1);}
int main()
{
cin>>n>>m>>k; memset(s,0x3f,sizeof(s));
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {cin>>c;
if (c=='1') g[i][++g[i][0]]=j;}
//~~~~~
for (int i=1;i<=n;i++)
{
int pm=g[i][0],ll=g[i][pm]-g[i][1]+1; s[i][0]=ll; s[i][pm]=0;
if (pm==0) continue; else
for (int p=1;p<=min(k,g[i][0]);p++)//skip p classes in total
for (int j=0;j<=p;j++) if (pm-(p-j)>=j+1) s[i][p]=min(s[i][p],dis(i,pm-(p-j),j+1)); //skip j before
for (int p=0;p<=min(g[i][0],k);p++) s[i][p]=ll-s[i][p];
sum+=ll;
}
for (int i=1;i<=n;i++)
for (int j=k;j>=1;j--)
for (int p=0;p<=min(g[i][0],k);p++)
if (j>=p) f[j]=max(f[j],f[j-p]+s[i][p]);
cout<<sum-f[k]<<endl;
}
```