2019年湘潭大学程序设计竞赛

Problem A Who's better?

https://ac.nowcoder.com/acm/contest/893/A

题意：模拟ACM比赛计分规则

题解：模拟

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[2][3];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    for(int i=0;i<2;i++){
        for(int j=0;j<3;j++){
            scanf("%d",&a[i][j]);
        }
    }
    if(a[0][0]>a[1][0]){
        cout<<1<<endl;
    }else if(a[0][0]<a[1][0]){
        cout<<2<<endl;
    }else{
        if(a[0][1]<a[1][1]){
            cout<<1<<endl;
        }else if(a[0][1]>a[1][1]){
            cout<<2<<endl;
        }else{
            if(a[0][2]<a[1][2]){
                cout<<1<<endl;
            }else if(a[0][2]>a[1][2]){
                cout<<2<<endl;
            }else{
                cout<<"God"<<endl;
            }
        }
    }
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem B Number

https://ac.nowcoder.com/acm/contest/893/B

题意：

• 如果n的最后一位数码是0，那么她就把n除以10；
• 否则她把这个数加上1；
• 直到n变为一个不大于1的数。

给定n，请问需要做多少次操作？

题解：模拟

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        ans=0;
        while(n>1){
            while(n%10==0)ans++,n/=10;
            if(n<=1)
                break;
            n++;
            ans++;
        }
        cout<<ans<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem C Math Problem

https://ac.nowcoder.com/acm/contest/893/C

题意：已知整数a,除192的余数是1。求区间[L,R]之间满足条件的a的累加和是多少？

题解：规律

朴素打表（见代码注释）

证明：

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&l,&r);
//        ans=0;
//        ans=r/192-(l-1)/192;
//        if(r%192)
//            ans++;
//        if((l-1)%192)
//            ans--;
        //cnt=0;
//        sum=0;
//        for(ll i=l;i<=r;i++){
//            if((i*i*i)%192==1){
//                cnt++;sum+=i;
//                cout<<i<<endl;
//            }
//        }
        //cout<<sum<<endl;
        r=(r%192==0)?r/192:r/192+1;
        //r=r*192+1;
        l--;
        l=(l%192==0)?l/192:l/192+1;
        //l=l*192+1;
        //cout<<l<<" "<<r<<endl;
        cout<<r+r*(r-1)*96-l-l*(l-1)*96<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem D Stone

https://ac.nowcoder.com/acm/contest/893/D

题意：将所有的石子合并成一堆，你所消耗的体力最小是多少？

题解：贪心

石子数累加和 -最大一堆的石子数量

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
ll a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        ans=0;
        sum=0;
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]),ans=max(ans,a[i]),sum+=a[i];
        cout<<sum-ans<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem E Watermelon

https://ac.nowcoder.com/acm/contest/893/E

题意：

题解：

C++版本一

题解：原博客

先对于问题进行分析，我们假设，如果lililalala（以下简称拉拉）一定是第一个人的话，那问题就会变得很明确：拉拉后面的人要做到在经过x轮之后使得刚好把西瓜吃完。
所以，我们可以对给出的数据进行改造，使得拉拉变成我们想要的第一个人。
怎么改造呢？其实枚举就可以，从每个人吃一个到每个人吃自己的肚量逐一枚举。但由于a[i]的数据范围过大，需要进行一些特判：

if(mx-1>m){
     //如果拉拉前面的人数大于m,那就算每个人只吃一个也无***到拉拉
     printf("NO\n");
     continue;
 }
 if(mx-1<=m&&s[mx-1]>=m){
     //如果拉拉前面的人数小于等于m，并且肚量加起来大于等于m，那我一定有办法刚好吃掉m个
     printf("YES\n");
     continue;
 }

经过上面的特判，其实我们已经把枚举范围压缩到了小于m(1e6),在时间复杂度上是允许的。
然后我们就可以开始枚举：

int flag=0;
for(int i=mx-1;i<=s[mx-1];i++){//s为前缀和
    if(f(m-i)==1){//f为判断函数
        flag=1;
        break;
    }
}

函数中也加了特判：
1.如果x为0，那就是刚好轮到拉拉时没得吃.
2.如果拉拉吃掉西瓜之后，接下来每个人就算一人只吃一个也无法结束这轮，那就无解.

然后我们求出游戏进行的最大轮数r和最小轮数l，也就是除了拉拉外所有人一次只吃一个和除了拉拉外所有人每次都吃最多的轮数。

显然可得，当这两个轮数不同时必然有解，证明如下：

如果l!=r，那我们肯定有办法控制在任意(l+1,r)轮之间刚好结束,这样就能使得拉拉在下一轮开始无法吃到西瓜，从而胜利。

如果l=r呢？首先我们要考虑到如果 l 或 r 为刚好结束一轮，那样也是直接胜利。否则得话，我们吃再多或者再少也无法在其他轮次结束游戏，也就是说，我们无法使得轮到拉拉时西瓜，所以无解。

int f(LL x){
    if(x==0){
        return 1;
    }
    if(x<n-1+a[mx]){
        return 0;
    }
    if(x<=s[n])return 1;
    if(x%(n-1+a[mx])==0)return 1;
    LL l=x/s[n],r=x/(n-1+a[mx]);
    if(l!=r){
        return 1;
    }
    else{
        return 0;
    }

最后，最最重要的一个特判（因为少了这个特判我wa了22发并且没过！！），那就是：如果只有一个人，也就是只有拉拉自己时，必定是他打扫卫生（我恨啊！）。
 

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define FI first
#define SE second
#define PB push_back
#define POP pop_back
#define D double
#define endl '\n'
typedef pair<int,int> PII;
const LL INF=1e18,mod=100000000;
const int N=1e5+7;
int a[N];
LL s[N];
int mx;
int n,m;
int f(LL x){
    if(x==0){
        return 1;
    }
    if(x<n-1+a[mx]){
        return 0;
    }
    if(x<=s[n])return 1;
    if(x%(n-1+a[mx])==0)return 1;
    LL l=x/s[n],r=x/(n-1+a[mx]);
    if(l!=r){
        return 1;
    }
    else{
        return 0;
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        mx=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            if(a[mx]<a[i])mx=i;
            s[i]=s[i-1]+a[i];//前缀和
        }
        if(n==1){
            //如果只有拉拉一个人，那一定是他打扫卫生
            printf("YES\n");
            continue;
        }
        if(mx-1>m){
            //如果拉拉前面的人数大于m,那就算每个人只吃一个也无***到拉拉
            printf("NO\n");
            continue;
        }
        if(mx-1<=m&&s[mx-1]>=m){
            //如果拉拉前面的人数小于等于m，并且肚量加起来大于等于m，那我一定有办法刚好吃掉m个
            printf("YES\n");
            continue;
        }
        int flag=0;
        for(int i=mx-1;i<=s[mx-1];i++){
            if(f(m-i)==1){
                flag=1;
                break;
            }
        }
        if(flag==1){
            printf("YES\n");
        }
        else printf("NO\n");
    }
    return 0;
}

C++版本二

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p;
ll l,r,u,v;
ll ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        int pos=0;
        int maxl=0;
        sum=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum+=a[i];
            if(maxl<a[i]){
                maxl=a[i];
                pos=i;
            }
        }
        l=0;
        r=0;
        for(int i=1;i<pos;i++){
            l+=1;
            r+=a[i];
        }
        //l+=a[pos];
        //r+=a[pos];
        flag=0;
        while(l<=m){
            //cout<<pos<<" "<<l<<" "<<r<<endl;
            if(m<=r){
                flag=1;
                break;
            }
            l+=n-1+a[pos];
            r+=sum;
        }
        cout<<(flag||n==1?"YES":"NO")<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem F Black & White

https://ac.nowcoder.com/acm/contest/893/F

题意：对S字符串中，两个操作：0变成1，1变成0，求S在经过最多m次操作后的最大价值

题解：

C++版本一

题解：DP

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp;
int a[N];
char str[N];
int pos[2][N],num[2];
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        scanf("%s",str+1);
        ans=0;
        memset(pos,0,sizeof(pos));
        num[0]=num[1]=0;
        for(int i=1;i<=n;i++){
            if(str[i]=='0'){
                num[0]++;
                pos[0][num[0]]=i;
            }else{
                num[1]++;
                pos[1][num[1]]=i;
            }
            ans=max(ans,i-pos[1][max(0,num[1]-m)]);
            ans=max(ans,i-pos[0][max(0,num[0]-m)]);
        }
        cout<<ans<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：二分 + 前缀和

Problem G Truthman or Fakeman

https://ac.nowcoder.com/acm/contest/893/G

题意：

题解：二分图+建模

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v,w;
int ans,cnt,flag,temp,sum;
int vis[N],VIS[N];
char str;
struct node{
    int v,w;
    node(){};
    node(int _v,int _w):v(_v),w(_w){}
};
vector<node>G[N];
bool dfs(int u,int col){
    ++sum;
    cnt+=col;
    vis[u]=col;
    bool res=1;
    for(int i=0,j=G[u].size();i<j;i++){
        int v=G[u][i].v;
        int val=G[u][i].w?col:!col;
        if(vis[v]==-1){
            res&=dfs(v,val);
        }else{
            res&=val==vis[v];
        }
    }
    return res;
}
void DFS(int u){
    vis[u]=!vis[u];
    VIS[u]=1;
    for(int i=0,j=G[u].size();i<j;i++){
        int v=G[u][i].v;
        if(!VIS[v])DFS(v);
    }
}
 
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            G[i].clear();
            vis[i]=-1;
            VIS[i]=0;
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            G[u].push_back({v,w});
            G[v].push_back({u,w});
        }
        ans=1;
        for(int i=1;i<=n;i++){
            if(vis[i]==-1){
                sum=cnt=0;
                ans&=dfs(i,1);
                if(cnt+cnt<sum){
                    DFS(i);
                }
 
            }
        }
 
        if(ans){
            for(int i=1;i<=n;i++){
                cout<<vis[i];
            }
            cout<<endl;
        }else{
            cout<<-1<<endl;
        }
    }
 
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v,w;
int ans,cnt,flag,temp,sum,tot;
int vis[N],VIS[N],TF[N];
char str;
struct node{
    int v,w;
    node(){};
    node(int _v,int _w):v(_v),w(_w){}
};
vector<node>G[N];
bool dfs(int u,int col){
    ++sum;
    cnt+=col;
    vis[u]=col;
    VIS[u]=tot;
    bool res=1;
    for(int i=0,j=G[u].size();i<j;i++){
        int v=G[u][i].v;
        int val=G[u][i].w?col:!col;
        if(vis[v]==-1){
            res&=dfs(v,val);
        }else{
            res&=val==vis[v];
        }
    }
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            G[i].clear();
            vis[i]=-1;
            VIS[i]=0;
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            G[u].push_back({v,w});
            G[v].push_back({u,w});
        }
        ans=1;
        tot=0;
        for(int i=1;i<=n;i++){
            if(vis[i]==-1){
                sum=cnt=0;
                tot++;
                ans&=dfs(i,1);
                TF[tot]=cnt+cnt<sum;
            }
        }
        if(ans){
            for(int i=1;i<=n;i++){
                cout<<(TF[VIS[i]]^vis[i]);
            }
            cout<<endl;
        }else{
            cout<<-1<<endl;
        }
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem H Chat

https://ac.nowcoder.com/acm/contest/893/H

题意：

题解：

C++版本一 

题解：原博客

对题目进行分析，要求的是使女神总生气度不超过k的最小总上线时间，换句话说那就是（咕了女神k小时使得我们获得的最大不在线时间）。想到这点接下来就可以写了。

首先我们对每天女神在线时间的做个预处理，统计下前缀和和个数。

  scanf("%s",a+1);
    for(int j=1;j<=m;j++){
        if(a[j]=='0')f[j]=f[j-1];
        else f[j]=f[j-1]+1,cnt[i]++;
    }

然后假使咕了女神所有的在线时间，那我们得到的价值当然就是一整天了，也就是

    s[i][cnt[i]]=m;

然后，因为数据比较小，我们再直接跑个m方的暴力就可以求出在第i天咕女神x（x<cnt[i]）次所带来的最大休息时间。

for(int p=1;p<=m;p++){
     for(int q=p;q<=m;q++){
         s[i][cnt[i]-f[q]+f[p-1]]=max(s[i][cnt[i]-f[q]+f[p-1]],m-(q-p+1));
         /*
         (p,q)为我假设的在线时间，通过前缀和计算得出(p,q)之间的女神在线时长:f[q]-f[p-1].
         所以咕了女神的时间x即是 cnt[i]-(f[q]-f[p-1])
         然后我们因此获得的休息时间t是 m-(p-q+1)
         所以在这一天咕女神x小时获得的休息时间可以更新为 min(s[i][x],t)
         也就是 s[i][x]=min(s[i][x],t)
         */
     }
 }

算完所有天的情况后，就是一个背包了：已知每天咕女神 0到cnt[i] 小时所带来的价值，最多可以咕k个小时，请问我怎么取能使得到的价值最大？

因为每天只能选择一种情况，所以是分组背包，开个二维数组记录一下

显然可得我们取k个小时肯定是最优的，因为对于任意k-1的情况，我们可以在他的基础上再咕掉任意一个还没咕的小时，再向前推也是同理。

for(int i=1;i<=n;i++){//第i天
    for(int j=0;j<=cnt[i];j++){//咕女神j个小时
        for(int l=k;l>=j;l--){//从后往前更新
            ans[i][l]=max(ans[i][l],ans[i-1][l-j]+s[i][j]);
        }
    }
}

所以我们就求得了答案ans[n][k]

然后我们要求的是花的最小时间，也就是总时间减去最大休息时间，输出即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define FI first
#define SE second
#define PB push_back
#define POP pop_back
#define D double
#define endl '\n'
typedef pair<int,int> PII;
const LL INF=1e18,mod=100000000;
const int N=2e5+7;
int n,m,k;
char a[222];
int s[222][222];//第一维表示天数，第二维表示改天咕女神的小时数，也就是在第i天咕女神j小时获得的最大不在线时间
int f[222];//统计每天女神在线时长的前缀和用的滚动数组
int cnt[222];//女神每天的在线时长
int ans[222][222];//二维背包容器
int main()
{
    int t;
    cin>>t;
    while(t--){
        memset(s,0,sizeof(s));
        memset(cnt,0,sizeof(cnt));
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++){
            scanf("%s",a+1);
            for(int j=1;j<=m;j++){
                if(a[j]=='0')f[j]=f[j-1];
                else f[j]=f[j-1]+1,cnt[i]++;
            }
            s[i][cnt[i]]=m;
            for(int p=1;p<=m;p++){
                for(int q=p;q<=m;q++){
                    s[i][cnt[i]-f[q]+f[p-1]]=max(s[i][cnt[i]-f[q]+f[p-1]],m-(q-p+1));
                }
            }
        }
        int num=m*n;
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=n;i++){
            for(int j=0;j<=cnt[i];j++){
                for(int l=k;l>=j;l--){
                    ans[i][l]=max(ans[i][l],ans[i-1][l-j]+s[i][j]);
                }
            }
        }
        printf("%d\n",num-ans[n][k]);
    }
    return 0;
}

C++版本二

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r;
int ans,cnt[N],flag,temp,sum;
int v[N][N],dp[N][N],a[N];
char str[N][N];
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&p);
        memset(a,0,sizeof(a));
        memset(cnt,0,sizeof(cnt));
        memset(v,0,sizeof(v));
        for(int i=1;i<=n;i++){
            scanf("%s",str[i]+1);
            for(int j=1;j<=m;j++){
                if(str[i][j]=='1'){
                    a[++cnt[i]]=j;
                }
            }
            v[i][cnt[i]]=m;
            for(int j=0;j<cnt[i];j++){
                for(int k=1;k+j<=cnt[i];k++){
                    v[i][cnt[i]-j-1]=max(v[i][cnt[i]-j-1],m-a[k+j]+a[k]-1);
                }
            }
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            for(int j=0;j<=cnt[i];j++){
                for(int k=p;k>=j;k--){
                    dp[i][k]=max(dp[i][k],dp[i-1][k-j]+v[i][j]);
                }
            }
        }
        ans=n*m-dp[n][p];
        cout<<ans<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}