=-=以前背包没学好。。。居然是第一次做分组背包的题，咳咳
不过这题比较厉害的是它的预处理。。。
心态崩了，为什么有的时候一个回车会往下走这么多行
想删回车，一下子就删了一段，还不知道在哪撤回
mmp，就写一丢丢
枚举左右端点可以一起移动
要令value[i][num[i]]=m
然后背包的第二个循环是从大到小，不然就相当于在这一类物品中拿了多个东西
代码代码。。。生气
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
const int inf=999999999;
int dp[600],num[600],fin[600][600],value[600][600];
int main()
{
int n,m,v;
while(~scanf("%d%d%d",&n,&m,&v))
{
for(int i=1;i<=n;i++)//输入
{
int t=0;
for(int j=1;j<=m;j++)
{
//printf("test\n");
char a;
scanf(" %c",&a);
if(a=='1')fin[i][++t]=j;//fin[i][j]存第i天第j节课在第几节
}
num[i]=t;//num[i]存储第i天课的数量
}
for(int i=1;i<=n;i++)//计算value，即第i天翘n节课节约的最大时间
{
for(int j=0;j<=min(num[i],v);j++)
{
int res=inf;
int p,q;
for(int k=0;k<=j;k++)
{
p=k;q=j-k;//枚举左右端点，即左缩进p位右缩进q位
res=min(res,fin[i][num[i]-q]-fin[i][p+1]+1);
}
value[i][j]=m-res;
//printf("%d\n",value[i][j]);
}
value[i][num[i]]=m;
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)//背包部分
{
for(int j=v;j>=0;j--)
{
//printf("%d@\n",j);
for(int k=0;k<=min(num[i],j);k++)
{
dp[j]=max(dp[j],dp[j-k]+value[i][k]);//dp[i]为翘i节课能节约的最大时间
}//printf("%d\n",dp[j]);
}
}
printf("%d\n",n*m-dp[v]);
}
return 0;
}
=-=
