Chat（分組背包）

連結：https://ac.nowcoder.com/acm/contest/893/H

來源：牛客網

題目描述

在Casya生活的世界裡，一天由m個小時組成。

最近Casya的女神終于答應在接下來的n天中與Casya聊天,Casya非常激動。

在這n天中的每一天的每一個小時中女神可能會線上或者不線上，

某個小時如果女神如果線上且Casya線上的話他們就會開心的聊一個小時；

反之如果女神線上Casya沒有線上的話女神就會認為Casya放了她的鴿子而積累一點生氣度。

而Casya是個很懶惰的人，他每天隻願意上線一次，當他某天下線後就不願意再上線了。

換句話說，他每天線上的時間必須是連續的。

現在Casya已經知道每一天的每個小時女神是否會線上

Casya希望在這n天中女神的總生氣度不超過k，在此前提下Casya希望他的總上線時間最小。

假設每個小時Casya和女神要麼完整線上要麼完整不線上，請問Casya在這n天中最小的總上線時間是多少小時？

輸入描述:

第一行一個數字T(1≤T≤30)T(1≤T≤30)--樣例個數。

每個樣例第一行三個數字n,m,k(1≤n,m≤200,0≤k≤200)n,m,k(1≤n,m≤200,0≤k≤200)。
然後這n行，每行一個長度為m的隻含'0'和'1'的字元串，
第i個字元串的第j個字元為'0'代表女神第i天的第j個小時不線上，為'1'表示女神第i天的第j個小時線上。

保證所有樣例中∑n×m∑n×m不超過5×1055×105。           

輸出描述:

每個樣例輸出一行一個數字--Casya在這n天中最小的總上線時間           

示例1

輸入

複制

2  
2 5 1  
01001  
10110  
2 5 0  
01001  
10110             

輸出

5
8
           

說明

第一個樣例:
一種可行的方案:
Casya第一天隻在第2個小時上線，第五個小時女生線上而Casya不線上，生氣度積累1；
Casya第一天在第1、2、3、4個小時上線。
Casya的總上線時間是1+4=5。
第二個樣例:
隻能老老實實上線。
Casya第一天在第2、3、4、5個小時上線；
Casya第一天在第1、2、3、4個小時上線。
Casya的總上線時間是4+4=8。           

#include<bits/stdc++.h>
using namespace std;
int dp[205][205];
int d[205][205];
int a[205];
const int inf=0x3ffff;
int n,m,k;
void solve(string s,int p){//這裡需要好好的研究研究 
    int ss=0,ls=0;
    int aa[205];
    for(int i=0;i<m;i++)
        if(s[i]=='1')    aa[ss++]=i;
    a[p]=ss;
    int li,si;
    for(int i=0;i<ss;i++){
        for(int j=0;j<=i;j++){
            si=ss-(i-j+1);//保留j到i，産生了si個不高興度 
            li=(aa[i]-aa[j]+1);//線上小時 需要的線上時間 
            d[p][si]=min(d[p][si],li);//更新最小 
        }
    }
    d[p][ss]=0;//預處理d[i][j] 第i天産生j個不高興度的線上時間 
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(d,0x3f,sizeof(d));
        memset(dp,0x3f,sizeof(dp));
        string s;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<=k;i++)
            dp[0][i]=0;
        for(int i=1;i<=n;i++){
            cin>>s;
            solve(s,i);
        }
        for(int i=1;i<=n;i++)//第一循環 分組數 
		for(int p=k;p>=0;p--)//第二重循環 容量體積 
		for(int j=0;j<=a[i];j++)//第三重循環 屬于i組的j 
        if(p-j>=0)
			dp[i][p]=min(dp[i][p],dp[i-1][p-j]+d[i][j]);
        int ans=dp[n][0];
        for(int i=0;i<=k;i++)
            ans=min(ans,dp[n][i]);
        printf("%d\n",ans);
    }
}