【HDU】6017 - Girls Love 233（贪心 & dfs）

#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
#define PI acos(-1.0)
#define LL long long
#define MAXN 105
int Case;
int l,m,num;
int pos[MAXN];
int vis[MAXN][MAXN][MAXN];      //记录这个状态是否搜索过 
int dp[MAXN][MAXN][MAXN];       //表示处理到第i个2，还有j次，上个2在k位置 

int dfs(int k,int res,int pr)
{
    if (k > num)        //递归退出条件：处理到最后一个2
        return l-pr >= 2;
    if (vis[k][res][pr] == Case)        //如果这个状态搜索过，则直接取结果
        return dp[k][res][pr];
    vis[k][res][pr] = Case;     //这个初始化过程巧妙，用当前组数记录是否搜索过
//  dp[k][res][pr] = 0;
//上面这一步不能初始化为0，否则如果在dfs不成立的时候，把值返回上一步的时候，可能把上一步的dp值替换为1 
    dp[k][res][pr] = -INF;
    int ll = max(pr+1 , pos[k]-res);        //左边界
    int rr = min(l , pos[k]+res);       //右边界
    for (int i = ll ; i <= rr ; i++)        //在左边界到右边界搜索 
    {
        int cost = abs(pos[k]-i);
        dp[k][res][pr] = max(dp[k][res][pr] , dfs(k+1,res-cost,i)+(i-pr>=3)*(k>1));//非第一个2且和上一个2中间拉开2个位置 
    }
    return dp[k][res][pr];
}

int main()
{
    int u;
    scanf ("%d",&u);
    for (Case = 1 ; Case <= u ; Case++)
    {
        char str[MAXN];
        scanf ("%d %d",&l,&m);
        scanf ("%s",str+1);
        num = 0;
        for (int i = 1 ; i <= l ; i++)
        {
            if (str[i] == '2')
                pos[++num] = i;
        }
        if (num == 0)       //特判一下，如果没有2，dfs第一个2就会出错 
        {
            puts("0");
            continue;
        }
        m >>= 1;
        printf ("%d\n",dfs(1,m,0));
    }
    return 0;
}