hdu6376 度度熊剪纸条

不愧是百度，出个题都这么恶臭，垃圾百度。

Description

度度熊有一张纸条和一把剪刀。

纸条上依次写着 N 个数字，数字只可能是 0 或者 1。

度度熊想在纸条上剪 K 刀（每一刀只能剪在数字和数字之间），这样就形成了 K+1 段。

他再把这 K+1 段按一定的顺序重新拼起来。

不同的剪和接的方案，可能会得到不同的结果。

度度熊好奇的是，前缀 1 的数量最多能是多少。

input

有多组数据，读到EOF结束。

对于每一组数据，第一行读入两个数 NN 和 KK 。

第二行有一个长度为 N 的字符串，依次表示初始时纸条上的 N 个数。

0≤K<N≤10000

所有数据 NN 的总和不超过100000

output

对于每一组数据，输出一个数，表示可能的最大前缀 11 的数量。

Sample

2
3

分析

先吐槽一下，垃圾百度，题意有歧义。

比如这个 1001100011

我们剪开：1 00 11 000 11

拼起来 1111100000 前缀1的数量是 5，这是题目的意思。

显然的：

1.若第一个或最后一个是1，一次就能剪下第一段或最后一段。

2.中间的片段用两刀剪下。

假如有n个1片段，我们已经剪下了n-1，剩下的那个片段可以带着0，只露出一边1即可，也就是他的代价-1。

但我们不知道具体是那个片段。

那我们干脆k++就得了。

这个问题就可以转化成01背包了，每段1的个数为价值，剪的次数为体积

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100005;
int n, k, w[maxn], dp[maxn], v[maxn];
char s[maxn];
int main(){
    while(scanf("%d%d", &n ,&k) != EOF){
        int tot = 0;
        memset(dp, 0, sizeof(dp));
        memset(w, 0, sizeof(w));
        memset(v, 0, sizeof(v));
        scanf("%s", s+1);
        for(int i=1; i<=n; i++){//求出每段1的“价值”和“体积”
            if(s[i] == '1' && s[i-1] == '1') w[tot] ++;
            else if(s[i] == '1' && s[i-1] != '1') w[++tot] = 1, v[tot] = 2;
        }
        k++;
        if(s[1] == '1') v[1] = 1;
        if(s[n] == '1') v[tot] = 1;//这两种情况特判
        if(k == 1){//剪0次的时候（前面k++）了
            if(s[1] == '1') printf("%d
", w[1]);
            else printf("0
");
            continue;
        }
        for(int i=1; i<=tot; i++){//01背包，不多说
            for(int j=k; j>=v[i]; j--){
                dp[j] = max(dp[j], dp[j-v[i]]+w[i]);
            }
        }
        printf("%d
", dp[k]);
    }
    return 0;
}