（dp）hdoj6017-Girls Love 233

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

  1 #include <iostream>
  2 #include<bits/stdc++.h>
  3 #include <stack>
  4 #include <queue>
  5 #include <map>
  6 #include <set>
  7 #include <cstdio>
  8 #include <cstring>
  9 #include <algorithm>
 10 #include <math.h>
 11 using namespace std;
 12 typedef long long ll;
 13 typedef unsigned long long ull;
 14 const int MAX=1e5+5;
 15 int t,n,m;//数据组数，长度，体力
 16 int pos[105];//2的位置
 17 char a[105];
 18 int ge;//2的个数
 19 int dp[105][55][105];
 20 int i,j,k,s;
 21 int lo,an;
 22 int re=-1;
 23 bool can[105][55][105];//到这种情况的可能性
 24 int main()
 25 {
 26 //    freopen("Girls Love 233_pre.in", "r", stdin); freopen("Girls Love 233_pre.out", "w", stdout);
 27     scanf("%d",&t);
 28     while(t--)
 29     {
 30         scanf("%d %d %s",&n,&m,a+1);
 31         m/=2;
 32         ge=0;
 33         for(i=1;i<=n;i++)
 34         {
 35             if(a[i]=='2')
 36                 pos[++ge]=i;
 37         }
 38         if(ge==0)
 39         {
 40             printf("0
");
 41             continue;
 42         }
 43         pos[0]=0;
 44         pos[ge+1]=n+1;
 45         for(i=0;i<=ge+1;i++)
 46             for(j=0;j<=m+1;j++)
 47                 for(k=0;k<=n+1;k++)
 48                 {dp[i][j][k]=0;can[i][j][k]=false;}
 49 //        for(i=0;i<=m+1;i++)
 50 //            for(j=0;j<=n+1;j++)
 51 //                can[0][i][j]=true;
 52         for(i=1;i<=ge;i++)
 53             can[i][0][pos[i]]=true;
 54         for(j=1;j<=m;j++)
 55         {
 56             lo=pos[1]-j;
 57             if(lo)
 58                 can[1][j][lo]=true;
 59             lo=pos[1]+j;
 60             if(lo<=n)
 61                 can[1][j][lo]=true;
 62         }
 63         for(i=2;i<=ge;i++)
 64         {
 65             for(j=0;j<=m;j++)
 66                 for(k=0;k+j<=m;k++)
 67             {
 68                 lo=pos[i]-k;
 69                 if(lo>0)
 70                 {
 71                     for(s=1;s<lo;s++)
 72                     {
 73                         if(can[i-1][j][s])
 74                         {
 75                             if(!can[i][j+k][lo])
 76                                 can[i][j+k][lo]=true;
 77                             an=dp[i-1][j][s];
 78                             if(lo-s>=3)
 79                             {
 80                                 an++;
 81                             }
 82                             dp[i][j+k][lo]=max(dp[i][j+k][lo],an);
 83                         }
 84                     }
 85                 }
 86                 lo=pos[i]+k;
 87                 if(lo+ge-i<=n)
 88                 {
 89                     for(s=1;s<lo;s++)
 90                     {
 91                         if(can[i-1][j][s])
 92                         {
 93                             if(!can[i][j+k][lo])
 94                                 can[i][j+k][lo]=true;
 95                             an=dp[i-1][j][s];
 96                             if(lo-s>=3)
 97                                 an++;
 98                             dp[i][j+k][lo]=max(dp[i][j+k][lo],an);
 99                         }
100                     }
101                 }
102             }
103         }
104         int an=-1;
105         int re;
106         for(i=0;i<=m;i++)
107         {
108             for(j=1;j<=n;j++)
109             {
110                 if(can[ge][i][j])
111                 {
112                     re=dp[ge][i][j];
113                     if(j<=n-2&&ge>0)
114                         re++;
115                     an=max(re,an);
116                 }
117             }
118         }
119         printf("%d
",an);
120     }
121     return 0;
122     }

View Code



开学前一天，踌躇满志，去自习，本计划着做几道题，结果上午开始就一直卡在这个题目上……

10：30 开始做题
12：42 懵逼
13：40 发现2222一类的情况有问题
14：40 准备重写第三遍
15：05 准备重写第四遍
15：34 还是WA 真的有点崩溃了
15：46 通过对拍找到问题所在，终于AC了



题目本身其实也没有非常复杂，只能说是自己现在太差。没有办法，以此勉励自己吧。不抛弃，不放弃！