Girls Love 233

Accepts: 30

Submissions: 218

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

除了翘课以外，结识新的妹子也是呃喵重要的日程安排之一。

这不，呃喵又混进了一个叫做ACgirls的女生群里，来达成自己不可描述的目的。

然而，呃喵只会喵了个咪地说话，于是很容易引起注意。为了掩饰自己的真实身份，呃喵每次说话都小心翼翼。

她知道，很多女生都喜欢说"233"，然而呃喵想说的话一开始就确定好了，所以她要对这句话做修改。

这句话的长度为n，语句里的字符不是'2'就是'3'。

呃喵的智力非常有限，只有m点。她每次操作可以交换两个相邻的字符，然而代价是智力-2。

现在问你，在使得自己智力不降为负数的条件下，呃喵最多能使这个字符串中有多少个子串"233"呢？

如"2333"中有一个"233"，"232323"中没有"233"

输入描述

第一行为一个整数T，代表数据组数。

接下来，对于每组数据——

第一行两个整数n和m，分别表示呃喵说的字符串长度 以及呃喵的智力

第二行一个字符串s，代表呃喵具体所说的话。

数据保证——

1 <= T <= 1000

对于99%的数据，1 <= n <= 10, 0 <= m <= 20

对于100%的数据，1 <= n <= 100, 0 <= m <= 100

输出描述

对于每组数据，输出一行。

该行有1个整数，表示最多可使得该字符串中有多少个"233"

输入样例

输出样例

2

1

2

一直没有思路，然后看了题解。。。

思路：和官方题解思路差不多。记忆化搜索。用时间戳来避免重复的memset。

做了这些比较基础的分析之后，基于数据规模很小，我们可以用以下4个要素表示完整的状态：

1.处理到第几个'2'

2.上一个'2'停留在什么位置，如果当前的'2'与上一个'2'距离相差>=2时则对答案+1

3.呃喵的剩余交换次数是多少

4.当前已经成功得到几个"233"

而这四个要素的大小，最坏情况下分别是n、n、m、n级别的数，我们随便以3个要素作为下标对应状态，使得第4个要素最优做DP. 转移的时候步长也是不超过2m的，所以很容易就可以得出复杂度为O(n * n * m/2 * m)的算法。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<stdlib.h>

using namespace std;

char num[];

int dp[][][],dfn[][][];

int p2[],cnt2,len,cas;

int dfs(int n,int lp,int tim)

{

    if(n>cnt2)

        return (len-lp>=);

    if(dfn[n][lp][tim]==cas)

        return dp[n][lp][tim];

    int l=max(lp+,p2[n]-tim);

    int r=min(len,p2[n]+tim);

    dp[n][lp][tim]=-1e9;    //这个地方赋值为-1就会wa，不知道为啥。。。

    dfn[n][lp][tim]=cas;

    for(int i=l;i<=r;i++)

    {

        int cost=abs(p2[n]-i);

        dp[n][lp][tim]=max(dp[n][lp][tim],dfs(n+,i,tim-cost)+(i-lp>=)*(n>));

    }

    return dp[n][lp][tim];

}

int main()

{

    int t;

    scanf("%d",&t);

    for(cas=;cas<=t;cas++)

    {

        int n,m;

        scanf("%d%d%s",&n,&m,num+);

        len=n;

        m/=;

        cnt2=;

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

            if(num[i]=='')

                p2[++cnt2]=i;

        if(cnt2==)

        {

            puts("");

            continue;

        }

        int ans=dfs(,,m);

        printf("%d\n",ans);

        //cout<<dp[1][0][m/2]<<endl;

    }

    return ;

}

巴特西

HDU_6017_Girls love 233_(dp)(记忆化搜索)

Girls Love 233

最新文章

热门文章