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

本文主要是介绍【HDU】6017 - Girls Love 233（贪心 dfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点击打开题目
这里写图片描述
题意：

第一想法是爆搜，虽然加了点优化，也想到相同的数字交换是没有意义的，但是还是RE爆栈了。后来看了出题人的解释，用了记忆化搜索的方法才AC，对我来说确实是个好题！

代码如下：

#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)        //递归退出条件：处理到最后一个2return 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;
}