hiho 有序01字符串 dp

题目1 : 有序01字符串

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

对于一个01字符串，你每次可以将一个0修改成1，或者将一个1修改成0。那么，你最少需要修改多少次才能把一个01串 S 变为有序01字符串(有序01字符串是指满足所有0在所有1之前的01串)呢？

输入

第一行是一个整数 T，代表测试数据的组数。(1 ≤ T ≤ 10)

以下T行每行包含一个01串 S 。(1 ≤ |S| ≤ 1000)

输出

对于每组测试数据输出最少需要修改的次数。

样例输入

样例输出

0

1

1
思路：找到1的时候考虑是否改成0；
　　　min（1后面的字符串最小改变值+1，1后面的0的个数；

#include<bits/stdc++.h>

using namespace std;

#define ll __int64

#define mod 1000000007

#define pi (4*atan(1.0))

const int N=2e3+,M=1e6+,inf=1e9+;

char a[N];

int zero[N],x;

int dp(char *a,int len)

{

    if(len==)

    return ;

    for(int i=;i<x;i++)

    if(a[i]=='')

    return min(dp(a+i+,len-i-)+,zero[x-len+i]);

    return ;

}

int main()

{

    int y,z,i,t;

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s",a+);

        x=strlen(a+);

        memset(zero,,sizeof(zero));

        for(i=x;i>=;i--)

        if(a[i]=='')

        zero[i-]=zero[i]+;

        else

        zero[i-]=zero[i];

        printf("%d\n",dp(a+,x));

    }

    return ;

}

巴特西

hiho 有序01字符串 dp

题目1 : 有序01字符串

描述

输入

输出

最新文章

热门文章