Bestcoder#92&HDU 6017 T3 Girl loves 233 DP

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"

输入样例

3
6 2
233323
6 1
233323
7 4
2223333

输出样例

2
1
2

思路

方法一：

  (1)交换2和2或交换3和3 是一种浪费

  所以我们得到一个贪心原则

结果中的2的先后顺序一定和原字符串中的2的先后顺序是一样的

什么，听说你想举反例？

假设第i个2和第i+1个2 的先后顺序交换了

那么在交换的过程中必定会有‘22’之间的交换，那么这样不换了既不会改变顺序，也是同样的结果

所以贪心原则是成立的！

(2)用p[i]表示第i个2在p[i]，假设全是3，然后我们一个一个确定2的位置

判定原则

 如果前一个2后当前2位置相差3那么就有一个233

(3)基于(1)的贪心原则划分阶段，用f[i,j,p]表示处理完第i个2，花j次交换，第i个2在p时最多的233个数

lj表示上次j的位置，lp表示上一次2的位置，那么：

后面的条件保证现在的位置在lp之后3个以及以上（保证贪心原则和判定原则）

可以用递归实现

 

program gl233;
uses math;
const
  inf='233.in';
  outf='233.out';
var
  n,m,ii,t,tot:longint;
  tmp:char;
  p:array[1..100] of longint;
  check,f:array[0..100,0..100,0..50] of longint;

procedure init;
var
  i:longint;
begin
  tot:=0;
  readln(n,m);
  for i:= 1 to n do
  begin
    read(tmp);
    if tmp='2' then
    begin
      inc(tot);
      p[tot]:=i;
    end;
  end;
end;

function pd233(app,i:longint):longint;
begin
    if i<=1 then exit(0);
    if app>=3 then exit(1)
      else exit(0);
end;

function find(i,lp,iq:longint):longint; //lp=last_p;   iq ?
var
  s,e,t1:longint;
begin

  if i>tot then if n-lp>=2 then exit(1) else exit(0);
   if check[i,lp,iq]<>i then check[i,lp,iq]:=ii
     else exit(f[i,lp,iq]);

  s:=max(p[i]-iq,lp+1);
  e:=min(p[i]+iq,n);
   for t1:=s to e do
     f[i,lp,iq]:=max(f[i,lp,iq],find(i+1,t1,iq-abs(t1-p[i]))+pd233(t1-lp,i));
   exit(f[i,lp,iq]);

end;

begin
  //assign(input,inf);
  //assign(output,outf);
  reset(input);
  rewrite(output);

  readln(t);
  for ii:= 1 to t do
   begin
     init;
     m:=m div 2;
     writeln(find(1,0,m));
   end;

  close(input);
  close(output);
end.

But! pascal会TLE 于是我们要用claris的方法！

还是上面那贪心原则
然后官方题解已经讲的很清楚了

最后还要提下，claris老师提供了一个复杂度更加优秀的O(n * n * n * 3)的做法，大体如下——

考虑最后形成的串是'2'与'3'归并排序后的结果。

于是我们显然需要知道——

1.当前选了多少个2

2.当前选了多少个3

3.当前用了多少次交换

4.影响决策的状态，这里有3种情况——

a.不存在前一个'2'，或者前一个'2'后面已经有了足够的'3'，记做状态0

b.前一个'2'后面只有0个'3'，记做状态1

c.前一个'2'后面只有1个'3'，记做状态2

用g2与g3表示2与3个个数，用p[]记录所有2的位置，于是就可以有——

for(i)for(j)for(k)for(t)if(~f[i][j][k][t])

{
    if (i < g2)//我们可以考虑接下来放置一个'2'
    {
        int sum = k + abs(i + j + 1 - p[i + 1]);
        if (sum <= m)gmax(f[i + 1][j][sum][1], f[i][j][k][t]);
    }
    if (j < g3)//我们可以考虑接下来放置一个'3'
    {
        int sta = t; int cnt = f[i][j][k][t];
        if (sta)
        {
            if (sta < 2)++sta;
            else sta = 0, ++cnt;
        }
        gmax(f[i][j + 1][k][sta], cnt);
    }
}最后在f[g2][g3][0~m][0~2]中更新答案。

program gl233;
uses math;
const
  inf='233.in';
  outf='233.out';
var
  n,m,ii,t,tot,num3,num2,sta,cnt,next:longint;
  tmp:char;
  p:array[1..100] of longint;
  check,f:array[0..100,0..100,0..50,0..2] of int64;

procedure init;
var
  i:longint;
begin
  tot:=0;
  readln(n,m);
  for i:= 1 to n do
  begin
    read(tmp);
    if tmp='2' then
    begin
      inc(tot);
      p[tot]:=i;
    end;
  end;
  num2:=tot;
  num3:=n-tot;
end;

procedure find; 
var
  i,j,k,t,ans:longint;
begin
  for i:=0 to num2 do
    for j:= 0 to num3 do
      for k:= 0 to m do
        for t:= 0 to 2 do
         f[i,j,k,t]:=-1;    //初始化为-1便于后面max

  f[0,0,0,0]:=0;            //边界
  for i:=0 to num2 do  
    for j:= 0 to num3 do
      for k:= 0 to m do
        for t:= 0 to 2 do
         if f[i,j,k,t]<>-1 then  //f[i,j,k,t]已经是一个更新过的状态
          begin
            if i<num2 then       //有足够的2，下一个放2
            begin
                next:=k+abs(i+j+1-p[i+1]);   //i+j+1是当前点
                if next<=m then f[i+1,j,next,1]:=max(f[i+1,j,next,1],f[i,j,k,t]);  //更新i+1个点
            end;
            if j<num3 then       //有足够的3，下一个放3
            begin
                cnt:=f[i,j,k,t]; 
                sta:=0;
                //t=0前面已经有足够3，那不用加233的个数
                if t=1 then sta:=2;      //前面有0个3又放了一个3，那么就有1个233啦
                if t=2 then inc(cnt);    //前面有1个3又放了一个3 ,那么就多了一个233
                //sta<>1因为放了3 那就不会有0个3 了

                f[i,j+1,k,sta]:=max(f[i,j+1,k,sta],cnt);   //更新
            end;
          end;

    ans:=0;
      for k:= 0 to m do
        for t:= 0 to 2 do
          ans:=max(ans,f[num2,num3,k,t]);  //findmax！
    writeln(ans);
end;

begin
  //assign(input,inf);
 // assign(output,outf);
  reset(input);
  rewrite(output);

  readln(t);
  for ii:= 1 to t do
   begin
     init;
     m:=m div 2;
     find;
   end;

  close(input);
  close(output);
end.